Фундаментальные структуры данных. АВЛ-деревья. Метод «преобразуй и властвуй», страница 4

Насколько эффективен данный алгоритм в наихудшем случае? Предположим для простоты, что n = 2↑k – 1, так что дерево пирамиды заполнено, т.е. на каждом уровне находится максимально возможное количество узлов. Пусть h – высота пирамиды; согласно первому свойству пирамид, h = log2n (или просто (log2(n+1))-1= k-1 для рассматриваемого нами значения n). В наихудшем случае при выполнении алгоритма построения пирамиды каждый ключ на уровне i дерева будет перемещаться до уровня листа h. Поскольку перемещение на один уровень вниз требует двух сравнений, общее количество сравнений ключей, выполняемых при перемещении ключа на уровне i, равно 2(h-i).

Пирамиды

Таким образом, общее количество сравнений ключей в наихудшем случае составляет Cworst(n) = ∑∑ 2*(h-i) = ∑ 2*(h-i)*(2↑i) = 2(n-log2(n+1)) Таким образом, при использовании восходящего алгоритма пирамида размером n может быть построена с выполнением менее чем 2n сравнений. Альтернативный (и менее эффективный) алгоритм строит пирамиду путем последовательных вставок нового ключа в ранее построенную; некоторые авторы называют этот алгоритм нисходящим построением пирамиды.

Пирамиды

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

Пирамиды

• Очевидно, что такая вставка не может требовать большего количества сравнений ключей, чем высота пирамиды. Поскольку высота пирамиды с n узлами около log2n, временная эффективность вставки составляет О(log2n).
• Рассмотрим теперь удаление корневого ключа пирамиды, которое можно выполнить при помощь следующего алгоритма:
• Обменяем ключ в корне с последним ключом пирамиды.
• Уменьшим размер пирамиды на 1.
• «Пирамидизируем» уменьшенное дерево путем перемещения К вниз по дереву так же, как мы делали в восходящем алгоритме.

Пирамиды

Эффективность операции удаления определяется количеством выполняемых сравнений ключей, необходимых для «пирамидизации» дерева после того, как был сделан обмен и размер пирамиды был уменьшен на 1. Поскольку не может потребоваться сравнений больше, чем удвоенная высота пирамиды, временная эффективность удаления из пирамиды – О(log2n).

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

Теперь мы можем рассмотреть пирамидальную сортировку (heapsort) – интересный алгоритм сортировки, открытый Дж. Вильямсом (J.W.J. Williams) в 1964 г. Этот двухэтапный алгоритм работает следующим образом. Этап 1. Построение пирамиды. Строим пирамиду для заданного массива. Этап 2. Удаление наибольших элементов. Применяем операцию удаления корня n-1 раз. В результате элементы массива удаляются в порядке уменьшения.

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

Поскольку мы уже знаем, что этап построения пирамиды алгоритма пирамидальной сортировки занимает время О(n), осталось выяснить временную эффективность второго этапа. Для количества сравнений ключей С(n), необходимого для удаления корневых ключей из пирамид уменьшающегося от n до 2 размера, получаем следующее неравенство: C(n) ≤ 2*log2(n-1) + 2*log2(n-2) + … + 2*log21 ≤ 2*∑log2i ≤ 2*∑log2(n-1) = 2*(n-1)*log2(n-1) ≤ 2n*log2n. Это означает, что для второго этапа пирамидальной сортировки С(n) Є O(n*log2n).

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

Таким образом, временная эффективность пирамидальной сортировки попадает в тот же класс, что и сортировка слиянием, но, в отличие от последней, выполняется «на месте», без привлечения дополнительной памяти. Эксперименты, проведенные над случайными файлами, показывают, что пирамидальная сортировка работает медленнее быстрой, однако вполне может соперничать с сортировкой слиянием.

Спасибо за внимание