Page 60 - 6110
P. 60
Після кожного обміну розмір купи зменшують на одиницю. В кінці
отримують повністю відсортований неспадний масив:
Heapsort(A)
1 Build_Max_Heap(A)
2 for downto 2
3 do Поміняти
4
5 Max_Heapify(A,1)
Час роботи процедури Heapsort рівний Т(n log n),
оскільки всього потрібно n-1 викликів Max_Heapify, кожен з
яких працює за Т(log n).
Контрольні запитання
1 Яким терміном в інформатиці називають спеціалізовану
деревовидну структуру даних, в якій існують певні властивості
впорядкованості?
2 Які базові операції з купою Вам відомі?
3 Яка властивість незростаючої купи?
4 Який принцип побудови неспадної купи?
5 Яка властивість неспадної купи?
59
