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

Элементом кучи с наименьшим ключом является ее корень, так что поиск мини- мального элемента выполняется за время 0(1). Как происходит добавление или удаление элементов кучи? Допустим, в кучу добавляется новый элемент v, а куча H на данный момент содержит n < N элементов.
После добавления она будет содер- жать n + 1 элементов. Начать можно с добавления нового элемента v в последнюю позицию i = n + 1, для чего выполняется простое присваивание H[i] = v. К сожале- нию, при этом нарушается основное свойство кучи, так как ключ элемента v может быть меньше ключа его родителя. Полученная структура данных почти является кучей, если не считать небольшой «поврежденной» части, где в конце был вставлен элемент v.

Для восстановления кучи можно воспользоваться несложной процедурой. Пусть j = paгent(/) = |f У 2] является родителем узла У, а Н\j] = w. Если kеу[v] < kеу[w], позиции v и w просто меняются местами. Перестановка восстанавливает свойство кучи в позиции i, но может оказаться, что полученная структура нарушает свойство кучи в позиции j, — иначе говоря, место «повреждения» переместилось вверх от i к j. Рекурсивное повторение этого процесса от позиции j = parent(i) продолжает восстановление кучи со смещением поврежденного участка вверх.

На рис. 2.4 показаны первые два шага процесса после вставки.

Рис. 2.4. Восходящий процесс восстановления кучи. Ключ 3 в позиции 16 слишком мал (слева). После перестановки ключей 3 и 11 нарушение структуры кучи сдвигается на один шаг

к корню дерева (справа)


Heapify-up(H,i):

Если У > 1

Присвоить j = parent (?) = [У/2]

Чтобы понять, почему эта процедура работает и в конечном итоге приводит к восстановлению порядка, полезно вникнуть структуру «слегка поврежденной» кучи в середине процесса. Допустим, 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) исправляет структуру кучи за время О(log i) при условии, что массив H является псевдокучей со слишком малым ключом H[i]. Использование Heapify-up позволяет вставить новый элемент в кучу из n элементов за время О(log n).

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

Итак, по принципу индукции рекурсивное применение Heapify-up( j) приведет к формированию кучи, как и требовалось. Процесс проходит по ветви от позиции i до корня, а значит, занимает время О(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 изображены первые шаги этого процесса.

Рис. 2.5. Нисходящий процесс восстановления кучи. Ключ 21 в позиции 3 слишком велик (слева). После перестановки ключей 21 и 7 нарушение структуры кучи сдвигается на один шаг

к низу дерева (справа)


Heapify-down(H, i):

Присвоить n = length(H)

Если 2i > n

Завершить выполнение без изменения H Иначе Если 2i < n

Присвоить left = 2i и right = 2i + 1

Присвоить j индекс для минимизации key[H[left]] и key[H[right]] Иначе Если 2i= n Присвоить j = 2i Конец Если

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

Поменять местами элементы H[i] и H[j]

Heapify-down(H, j)

Конец Если

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

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

Доказательство. Для доказательства того, что этот процесс исправляет струк- туру кучи, будет использован процесс обратной индукции по значению i. Пусть n — количество элементов в куче. Если 2i > n, то, как было указано выше, H уже яв- ляется кучей и доказывать ничего не нужно. В противном случае пусть j является дочерним узлом i c меньшим значением ключа, а w = Hj]. Перестановка элементов массива w и v выполняется за время 0(1). После перестановки массив H пред- ставляет собой либо кучу, либо псевдокучу со слишком большим ключом H[j] = v. Это утверждение истинно, поскольку присваивание key(v) = key(w) превращает H в кучу. Теперь j > 2i, поэтому по предположению индукции рекурсивный вызов Heapify-down восстанавливает свойство кучи.

Алгоритм многократно перемещает элемент, находящийся в позиции i, вниз по ветви, поэтому за О(log n) итераций будет сформирована куча.

Чтобы использовать этот процесс для удаления элемента v = H[i] из кучи, мы заменяем H[i] последним элементом массива, H[n] = w. Если полученный массив не является кучей, то это псевдокуча со слишком малым или слишком большим значением ключа H[i]. Использование процедуры Heapify-up или Heapify-down при- водит к восстановлению свойства кучи за время О(log n). ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация операций с кучей:

  1. Пока вы не интегрируете в своё сознание то, что вы уже получили, оно становится кучей мусора в вашем уме, который не всегда вам полезен.
  2. ОПЕРАЦИЯ
  3. ОПЕРАЦИЯ ФОРМАЛЬНАЯ
  4. ОПЕРАЦИЯ ИНТЕЛЛЕКТУАЛЬНАЯ
  5. ОПЕРАЦИЯ КОНКРЕТНАЯ
  6. ОПЕРАЦИЯ СОЗНАТЕЛЬНАЯ
  7. Действия, операции и психологические приемы.
  8. § 2. Правовое регулирование валютных операций
  9. ОПЕРАЦИЯ ПРИСПОСОБИТЕЛЬНАЯ
  10. 6. Договоры об отдельных транспортно-экспедиционных операциях и услугах
  11. 5. Внешнеэкономические подрядные операции с давальческим сырьем
  12. Статья 1068. Операции со счетом, которые выполняются банком
  13. Статья 213. Нарушение порядка осуществления операций с металлоломом
  14. Статья 1101. Сообщение о проведенных операциях
  15. 4.1. Содержание основных задач и операций, выполняемых специалистом:
  16. Глава 6. Реализация права
  17. 10. Реализация заложенного имущества
  18. 4.2. Реализация
  19. 4. Реализация прав по ипотеке
  20. 3.3. Дальнейшая реализация проекта