Стр. 89 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
87
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
< начальное построение пирамиды из x
1
,x
2
,…,x
n
>
for (i=n; i>=
2
; i--)
{
< меняем x
1
и x
i
>
<восстановление пирамиды на ключах x
1
– x
(i-
1
)
>
}
Осталось найти эффективный способ построения и восстановления
пирамиды. Заметим, что любое поддерево пирамиды также является пирамидой
(по определению).
Построение пирамиды
Сначала построим из ключей любое бинарное дерево. Пусть исходный
массив представляется в виде
91 48 58 94 34 18 85 93 10 75 51 44
Этому массиву соответствует следующее бинарное дерево, которое не
является пирамидой
91
48
58
94
93
34
75
10
51
18
44
85
Рис. 70. Бинарное дерево
Теперь преобразуем это дерево в пирамиду. Сделаем это рекурсивно.
Тривиальный случай: дерево или поддерево из одной вершины – всегда
пирамида.
Пусть для некоторого бинарного дерево оба поддерева уже являются
пирамидами. Тогда для того, чтобы дерево стало пирамидой, необходимо
произвести следующие действия:
1. Сравниваем корень с большим из сыновей. Если корень больше, то
дерево уже является пирамидой и делать ничего не надо.
2. Если корень меньше, то меняем его местами с большим сыном и
применяем данный алгоритм рекурсивно к тому поддереву, которое “испорчено
последней перестановкой”.
