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

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

Рисунок 2.4 – Работа процедуры Heapify(A, 2) при heap-size [ A ]= 10

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

Листинг 2.4 – Процедура восстановления основного свойства кучи

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

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

Эту же оценку можно получить так: на каждом шаге происходит спуск по дереву на один уровень, а высота дерева есть О (log n).