Реализация операций с кучей
Для восстановления кучи можно воспользоваться несложной процедурой. Пусть 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). ■
Еще по теме Реализация операций с кучей:
- Пока вы не интегрируете в своё сознание то, что вы уже получили, оно становится кучей мусора в вашем уме, который не всегда вам полезен.
- ОПЕРАЦИЯ
- ОПЕРАЦИЯ ФОРМАЛЬНАЯ
- ОПЕРАЦИЯ ИНТЕЛЛЕКТУАЛЬНАЯ
- ОПЕРАЦИЯ КОНКРЕТНАЯ
- ОПЕРАЦИЯ СОЗНАТЕЛЬНАЯ
- Действия, операции и психологические приемы.
- § 2. Правовое регулирование валютных операций
- ОПЕРАЦИЯ ПРИСПОСОБИТЕЛЬНАЯ
- 6. Договоры об отдельных транспортно-экспедиционных операциях и услугах
- 5. Внешнеэкономические подрядные операции с давальческим сырьем
- Статья 1068. Операции со счетом, которые выполняются банком
- Статья 213. Нарушение порядка осуществления операций с металлоломом
- Статья 1101. Сообщение о проведенных операциях
- 4.1. Содержание основных задач и операций, выполняемых специалистом:
- Глава 6. Реализация права
- 10. Реализация заложенного имущества
- 4.2. Реализация
- 4. Реализация прав по ипотеке
- 3.3. Дальнейшая реализация проекта