часть главы посвящена анализу этих операции и применению кучи в задачах сортировки и моделирования очереди с приоритетами. Перечислим основные операции над кучей:

•Процедура Heapify позволяет поддерживать основное свойство (7.1). Время работы составляет О (lgra).

•Процедура Build-Heap строит кучу из исходного (неотсортированного) массива. Время работы О (га).

•Процедура Heapsort сортирует массив, не используя дополнительной памяти. Время работы О (га lgra).

•Процедуры Extract-Max (взятие наибольшего) и Insert (добавление элемента) используются при моделировании очереди с приоритетами на базе кучи. Время работы обеих процедур составляет О (lgra).

Упражнения

7.1-1 Пусть куча имеет высоту h. Сколько элементов может в ней быть? (Укажите максимальное и минимальное значения.)

7.1-2 Докажите, что куча из га элементов имеет высоту lgraJ-

7.1-3 Докажите, что при выполнении основного свойства кучи корневая вершина любого поддерева является наибольшей в этом поддереве.

7.1-4 Где может находиться наименьший элемент кучи, если все её элементы различны?

7.1-5 Пусть массив отсортирован в обратном порядке (первый элемент - наибольший). Является ли такой массив кучей?

7.1-6 Является ли кучей массив (23,17,14, 6,13,10,1, 5, 7,12)?

7.2. Сохранение основного свойства кучи

Процедура Heapify - важное средство работы с кучей. Её параметрами являются массив А и индекс г. Предполагается, что поддеревья с корнями Left (г) и Right (г) уже обладают основным свойством. Процедура переставляет элементы поддерева с вершиной г, после чего оно обладает основным свойством. Идея проста: если это свойство не выполнено для вершины г, то её следует поменять с большим из её детей и т.д., пока элемент А[г] не «подгрузится» до нужного места.

Рис. 7.2 Работа процедуры Heapify(A, 2) при heap-size[A] = 10. (а) Начальное состояние кучи. В вершине г = 2 основное свойство нарушено. Чтобы восстановить его, необходимо поменять А[2] и А[4]. После этого (б) основное свойство нарушается в вершине с индексом 4. Рекурсивный вызов процедуры Heapify(A, 4) восстанавливает основное свойство в вершине с индексом 4 путём перестановки А[4] -н> А[9] (в). После этого основное свойство выполнено для всех вершин, так что процедура Heapify(A, 9) уже ничего не делает.

Работа процедуры Heapify показана на рис. 7.2. В строках 3-7 в переменную largest помещается индекс наибольшего из элементов А[г], A[Left(«)] и A[RlGHT(i)]. Если largest = г, то элемент А[г] уже «погрузился» до нужного места, и работа процедуры закончена. Иначе процедура меняет местами A[i] и A[largest] (что обеспечивает выполнение свойства (7.1) в вершине г, но возможно, нарушает

это свойство в вершине largest) и рекурсивно вызывает себя для вершины largest, чтобы исправить возможные нарушения.

Оценим время работы процедуры Heapify. На каждом шаге требуется произвести 0(1) действий, не считая рекурсивного вызова. Пусть ТЫ) - время работы для поддерева, содержащего га элементов. Если поддерево с корнем г состоит из га элементов, то поддеревья с корнями left(i) и Шснт(г) содержат не более чем по 2га/3 элементов каждое (наихудший случай - когда последний уровень в поддереве заполнен наполовину). Таким образом,

ТЫ) Т(2га/3) + 0(1)

Из теоремы 4.1 (случай 2) получаем, что ТЫ) = O(lgra). Эту же оценку можно получить так: на каждом шаге мы спускаемся по дереву на один уровень, а высота дерева есть О (lgra).

Упражнения

7.2-1 Покажите, следуя образцу рис. 7.2, как работает процедура Heapify(A, 3) для массива (27,17, 3,16,13,10,1, 5, 7,12,4, 8, 9, 0).

7.2-2 Пусть элемент А[г] больше, чем его дети. Каков будет результат вызова процедуры Heapify(A, г)?

7.2-3 Пусть г > heap-size[A]/2. Каков будет результат вызова процедуры Heapify(A, г)?

7.2-4 Измените процедуру Heapify, заменив рекурсию циклом. (Некоторые компиляторы при этом порождают более эффективный код.)

7.2-5 Докажите, что наибольшее время работы процедуры Heapify для кучи из га элементов равно S7(lgra). (Указание: приведите пример, когда процедура вызывается для каждой вершины на пути от корня к листу).

7.3. Построение кучи

Пусть дан массив А[1. .га], который мы хотим превратить в кучу, переставив его элементы. Для этого можно использовать проЦеДУРУ Heapify, применяя её по очереди ко всем вершинам, начиная с нижних. Поскольку вершины с номерами [п/2\ + 1,.. .,га являются листьями, поддеревья с этими вершинами удовлетворяют основному свойству. Для каждой из оставшихся вершин, в порядке убывания индексов, мы применяем процедуру Heapify. Порядок обработки вершин гарантирует, что каждый раз условия вызова