Page 59 - 6110

8 if
9 then Поміняти
10 Max_Heapify(A,largest)

Час роботи процедури в найгіршому випадку пропорційний
висоті купи. Якщо купа складається з n елементів, то її висота
log 2(n) . Тому оцінка часу роботи одного визову Max_Heapify є
Т(log n).
Для падтримки властивості неспадної бінарної купи можна
скористатись процедурою Min_Heapify. Вона повністю подібна
до Max_Heapify, тільки в рядках 3 і 6 алгоритму знак ">" треба
замінити на "<".
За допомогою процедури Max_Heapify можно перетворити
масив A[1..n], де n = length[A], у незростаючу купу. Всі
елементи підмасиву є листами дерева,
тому кожен з них можна вважати одноелементною купою, з якої
можна почати процес побудови. Процедура Build_Max_Heap
проходить по всім іншим вузлам і для кожного з них виконує
процедуру Max_Heapify:

Build_Max_Heap(A)

1
2 for downto 1
3 do Max_Heapify(A,i)

По завершенню роботи процедури, масив A організується в
незростаючу купу. Час роботи процедури Build_Max_Heap
можна записати так:

Для створення неспадної купи, необхідно замінити у третьому
рядку алгоритма виклик Max_Heapify на Min_Heapify.
Робота алгоритму сортування купи починається з віклику
процедури Build_Max_H, за допомогою якої з початкового масиву
A[1..n] створюється незростаюча купа. Далі послідовно з купи
виймається найбільший елемент, який міняють з останнім в купі.

58