процедуры (выполнение основного свойства для поддеревьев) будут выполнены.

Build-Heap (А)

1heap-size[A] +- length[A]

2for г f- [length[A]/2\ downto 1

3do Heapify(A, i)

Пример работы процедуры Build-Heap показан на рис. 7.3.

Ясно, что время работы процедуры Build-Heap не превышает О (га lgra). Действительно, процедура Heapify вызывается О (га) раз, а каждое её выполнение требует времени О (lgra). Однако эту оценку можно улучшить, чем мы сейчас и займёмся.

Дело в том, что время работы процедуры Heapify зависит от высоты вершины, для которой она вызывается (и пропорционально этой высоте). Поскольку число вершин высоты h в куче из га элементов не превышает [ra/2/l+1] (см. упр. 7.3-3), а высота все кучи не превышает [lg raj (упр. 7.1-2), время работы процедуры Build-Heap не превышает

л.=о

2h+i

0(h) = О U> (7.2)

Полагая х = 1/2 в формуле (3.6), получаем верхнюю оценку для суммы в правой части:

оо

h1/2

1 - 2.

2h (1-1/2)2

Таким образом, время работы процедуры Build-Heap составляет

= О(п).

Упражнения

7.3-1 Покажите, следуя образцу рис. 7.3, как работает процедура Build-Heap для массива А = (5, 3,17,10, 84,19,6,22, 9).

7.3-2 Почему в процедуре Build-Heap существенно, что параметр г пробегает значения от [length[A]/2\ до 1 (а не наоборот)?

7.3-3 Докажите, что куча из га элементов содержит не более [ra/2/l+1J вершин высоты h.

Рис. 7.3 Работа процедуры Build-Heap. Показано состояние данных перед каждым вызовом процедуры heapify в строке 3.

7.4. Алгоритм сортировки с помощью кучи

Алгоритм сортировки с помощью кучи состоит из двух частей. Сначала вызывается процедура Build-Heap, после выполнения которой массив является кучей. Идея второй части проста: максимальный элемент массива теперь находится в корне дерева (А[1]). Его следует поменять с А[п], уменьшить размер кучи на 1 и восстановить основное свойство в корневой вершине (поскольку поддеревья с корнями Left(1) и Right(I) не утратили основного свойства кучи, это можно сделать с помощью процедуры Heapify). После этого в корне будет находиться максимальный из оставшихся элементов. Так делается до тех пор, пока в куче не останется всего один элемент.

Heapsort(A)

1Build-Heap(A)

2for г f- length[A] downto 2

3do поменять A[l] +-> A[i]

4heap-size[A] f- heap-size[A] - 1

5Heapify(A, 1)

Работа второй части алгоритма показана на рис. 7.4. Изображены состояния кучи перед каждым выполнением цикла for (строка 2).

Время работы процедуры Heapsort составляет О (га lgra). Действительно, первая часть (построение кучи) требует времени О (га), а каждое из га - 1 выполнений цикла for занимает время О (lgra).

Упражнения

7.4-1 Покажите, следуя образцу рис. 7.4, как работает процедура Heapsort для массива А = (5,13, 2,25,7,17, 20,8,4).

7.4-2 Пусть исходный массив А уже отсортирован в порядке возрастания. Каково будет время сортировки с помощью кучи? А если массив был отсортирован в порядке убывания?

7.4-3 Докажите, что время работы процедуры Heapsort составляет Q (га lgra).

7.5. Очереди с приоритетами

На практике алгоритм сортировки с помощью кучи не является самым быстрым - как правило, быстрая сортировка (гл. 8) работает быстрее. Однако сама куча как структура данных часто ока-