2.4 Пирамидальная сортировка

2.4.1 Введение в алгоритм

Как и алгоритм сортировки слиянием, алгоритм пирамидальной сортировки требует времени О(п·log п) для сортировки п объектов, но обходится дополнительной памятью размера О(1) (вместо О(п) для сортировки слиянием). Таким образом, этот алгоритм сочетает преимущества двух ранее рассмотренных алгоритмов – сортировки слиянием и сортировки вставками.

Структура данных, которую использует алгоритм (она называется двоичной кучей) оказывается полезной и в других ситуациях. В частности, на её базе можно эффективно организовать очередь с приоритетами.

Термин «куча» иногда используют в другом смысле (область памяти, где данные размещаются с применением автоматической «сборки мусора» – напри­мер, в языках Lisp и C#).

Двоичной кучей (binary heap) называют массив с определёнными свойства­ми упорядоченности. Чтобы сформулировать эти свойства, будем рассматривать массив как двоичное дерево (рис. 2.3). Каждая вершина дерева соответствует элементу массива. Если вершина имеет индекс i, то её родитель имеет индекс (вершина с индексом 1 является корнем), а её дети – индексы (2i) и (2i + 1). Т.к. куча может не занимать всего массива, и поэтому нужно хранить не только массив А и его длину length[A], но также специальный па­раметр heap-size[A] (размер кучи), причём heap-size[A] ≤ length[A]. Куча состоит из элементов А[1],...,A[heap-size[A]]. Движение по дереву осуществляется процедурами:

Листинг 2.3 – Процедуры перемещения по дереву (реализация на базе массива)

Рисунок 2.3 – Интерпретации кучи: как дерево (а) или как массив (б)

Элемент А[1] является корнем дерева. В большинстве компьютеров для выполнения процедур Left и Parent можно использовать команды левого и правого сдвига (Left, Parent); Right требует левого сдвига, после которого в младший разряд помещается единица. Элементы, хранящиеся в куче, должны обладать основным свойством кучи (heap property): для каждой вершины i, кроме корня (т.е. при 2 ≤ i ≤ heap-size[A]),

Отсюда следует, что значение потомка не превосходит значения предка. Та­ким образом, наибольший элемент дерева (или любого поддерева) находится в корневой вершине дерева (этого поддерева).

Высотой (height) вершины дерева называется высота поддерева с корнем в этой вершине (число рёбер в самом длинном пути с началом в этой вершине вниз по дереву к листу). Высота дерева, таким образом, совпадает с высотой его корня. В дереве, составляющем кучу, все уровни (кроме, быть может, по­следнего) заполнены полностью. Поэтому высота этого дерева равна Θ(log n), где п – число элементов в куче. Время работы основных операций над кучей пропорционально высоте дерева и, следо­вательно, составляет O(log n). Оставшаяся часть главы посвящена анализу этих операций и применению кучи в задачах сортировки и моделирования очереди с приоритетами. Перечислим основные операции над кучей.

• Процедура Heapify позволяет поддерживать основное свойство («ребенок не больше своего родителя»). Время работы составляет O(log n).

• Процедура Build-Heap строит кучу из исходного (неотсортированного) мас­сива. Время работы O(п).

• Процедура HeapSort сортирует массив, не используя дополнительной памя­ти. Время работы O(nlog n).

• Процедуры Extract-Max (взятие наибольшего) и Insert (добавление эле­мента) используются при моделировании очереди с приоритетами на базе кучи. Время работы обеих процедур составляет O(log n).