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

Процедура 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).