Реализация операций с кучей

Элементом кучи с наименьшим ключом является ее корень, так что поиск мини- мального элемента выполняется за время O(1). Как происходит добавление или удаление элементов кучи? Допустим, в кучу добавляется новый элемент v, а куча H на данный момент содержит n < N элементов.

Для восстановления кучи можно воспользоваться несложной процедурой. Пусть j = parent(i) = является родителем узла i, а H[j] = w. Если key[v] < key[w], позиции v и w просто меняются местами.

Перестановка восстанавливает свойство кучи в позиции i, но может оказаться, что полученная структура нарушает свойство кучи в позиции j, — иначе говоря, место «повреждения» переместилось вверх от i к j. Рекурсивное повторение этого процесса от позиции j = parent(i) продолжает восстановление кучи со смещением поврежденного участка вверх.

Heapify-up(H,i):

Если i > 1

Присвоить j = parent(i) =

Если key[H[i]]<key[H[j]]

Поменять местами элементы H[i] и H[j] Heapify-up(H,j)

Конец Если Конец Если

Чтобы понять, почему эта процедура работает и в конечном итоге приводит к восстановлению порядка, полезно вникнуть структуру «слегка поврежденной» кучи в середине процесса. Допустим, H — массив, а v — элемент в позиции i. Бу- дем называть H псевдокучей со слишком малым ключом H[i], если существует такое значение α ≥ key(v), что повышение key(v) до α приведет к выполнению основно- го свойства кучи для полученного массива.

(Другими словами, элемент v в H[i] слишком мал, но повышение его до α решит проблему.) Важно заметить, что если H является псевдокучей со слишком малым корневым ключом (то есть H[1]), то в действительности H является кучей.

Чтобы понять, почему это утверждение ис- тинно, заметим, что если повышение H[1] до α превратит H в кучу, то значение H[1] также должно быть меньше значений обоих его дочерних узлов, — а следовательно, для H уже выполняется свойство порядка кучи.

(2.12) Процедура Heapify-up(H, i) исправляет структуру кучи за время O(log i) при условии, что массив H является псевдокучей со слишком малым ключом H[i]. Использование Heapify-up позволяет вставить новый элемент в кучу из n элементов за время O(log n).

Доказательство. Утверждение будет доказано методом индукции по i. Если  i = 1, истинность очевидна, поскольку, как было замечено ранее, в этом случае H уже является кучей. Теперь рассмотрим ситуацию с i > 1: пусть v = H[i], j = parent(i), w = H[j], и β = key(w). Перестановка элементов v и w выполняется за время O(1).

После перестановки массив H представляет собой либо кучу, либо псевдокучу со слишком малым ключом H[j] (теперь содержащим v). Это утверждение истинно, поскольку присваивание в узле j ключа β превращает H в кучу.

Итак, по принципу индукции рекурсивное применение Heapify-up( j) приведет к формированию кучи, как и требовалось. Процесс проходит по ветви от позиции i до корня, а значит, занимает время O(log i).

Чтобы вставить новый элемент в кучу, мы сначала добавляем его как последний элемент. Если новый элемент имеет очень большой ключ, то массив представляет собой кучу. В противном случае перед нами псевдокуча со слишком малым зна- чением ключа нового элемента. Использование процедуры Heapify-up  приводит  к восстановлению свойства кучи.

Теперь рассмотрим операцию удаления элемента. Во многих ситуациях с при- менением приоритетных очередей не нужно удалять произвольные элементы — только извлекать минимум. В куче это соответствует нахождению ключа в корне- вом узле (который содержит минимум) с его последующим удалением; обозначим эту операцию ExtractMin(H).

Теперь можно реализовать более общую операцию Delete(H, i), которая удаляет элемент в позиции i. Допустим, куча в данный момент содержит n элементов. После удаления элемента H[i] в куче останется n − 1 элемен- тов и помимо нарушения свойства порядка кучи в позиции i возникает «дыра», потому что элемент H[i] пуст.

Начнем с заполнения «дыры» в H и переместим элемент w из позиции n в позицию i. После этого массив H по крайней мере удовлетворяет требованию о том, что его первые n − 1 элементов находятся в первых n − 1 пози- циях, хотя свойство порядка кучи при этом может не выполняться.

Тем не менее единственным местом кучи, в котором порядок может быть на- рушен, является позиция i, так как ключ элемента w может быть слишком мал или слишком велик для позиции i. Если ключ слишком мал (то есть свойство кучи нарушается между узлом i и его родителем), мы можем использовать Heapify-up(i) для восстановления порядка.

С другой стороны, если ключ key[w] слишком велик, свойство кучи может быть нарушено между i и одним или обоими его дочерними узлами. В этом случае будет использоваться процедура Heapify-down, очень похожая на Heapify-up, которая меняет элемент в позиции i с одним из его дочерних узлов и продолжает рекурсивно опускаться по дереву. На рис. 2.5 изображены первые шаги этого процесса.