212
правок
Изменения
→Операции над последовательностью куч
==Операции над последовательностью куч==
При конструировании последовательности куч будем последовательно выполнять вставку в конец новых элементов. В итоге мы получим, что наш массив разбит на подмассивы размером <tex dpi = 120> L(k) </tex>. Для каждого подмассива выполним операцию '''heapify'''(она выполняется так же, как в [[Двоичная куча|двоичной куче]]), после которой необходимо будет отсортировать корни куч, чтобы выполнялся инвариант а при операции получении отсортированного массива будем удалять максимальный элемент из последовательности. Следовательно, нам необходимы четыре две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого размера), и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности, операция сортировки корней куч и восстановление инварианта последовательности.
Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти корень соседней кучи слева. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </tex>-ая куча Леонардо. Для хранения списка длин куч придется выделить <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти.
===Вставка элемента===
[[Файл:add-example.png|470px|thumb|right|Пример вставки элемента.(без просеивания вниз)]][[Файл:Leonardo-heap-2.png|470px|thumb|right|Вставка в последовательность куч, показанную выше, числа 13. Далее будет сразу происходить просеивание внутри "зеленого" дерева Леонардо, так как корень соседнего дерева меньше, чем дети корня "зелёного" дерева.]]
При добавлении в последовательность нового элемента возможны две ситуации:
* Если две последние кучи имеют размеры <tex dpi = 120> L(x + 1) </tex> и <tex dpi = 120> L(x) </tex> (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного <tex dpi = 120> L(x+2) </tex>. Для неё свойство кучи необязательно.
* Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером <tex dpi = 120> 1 </tex>. Этот размер полагается равным <tex dpi = 120> L(1) </tex>, кроме случая, когда крайняя правая куча уже имеет размер <tex dpi = 120> L(1) </tex>, тогда размер новой одноэлементной кучи полагают равным <tex dpi = 120> L(0) </tex>.
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
# Пока слева от неё есть куча, и значение её корня больше значения текущего корня и обоих корней куч-потомков:
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то модификация сортировки вставками будет работать за <tex dpi = 120> O(\log{N}) </tex>. Просеивание тоже выполняется за <tex dpi = 120> O(\log{N}) </tex>, тогда в итоге операция вставки выполняется за:
<tex dpi = 120> O(\log{N}) + O(\log{N}) = O(\log{N}) </tex>.
=== Уменьшение последовательности куч путём удаления элемента справа ===
Если размер крайней правой кучи равен <tex dpi = 120> 1 </tex> (то есть <tex dpi = 120> L(1) </tex> или <tex dpi = 120> L(0) </tex>), эта куча просто удаляется.
В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то восстановление свойства последовательности выполняется за <tex dpi = 120> O(\log{N}) </tex>.
===Восстановление свойств последовательности===
Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''prev''''' (возвращает индекс корня ближайшей слева кучи), '''''left''''' (возвращает индекс левого сына), '''''right''''' (возвращает индекс правого сына) уже реализованы. В функцию '''''ensureSequence''''' передается индекс корня кучи, с которой начинаем восстановление.
siftDown(i)
</code>
==Сложность==
