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>.
Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''prev''''' (возвращает индекс корня ближайшей слева кучи), '''''left''''' (возвращает индекс левого сына), '''''right''''' (возвращает индекс правого сына) уже реализованы. В функцию '''''ensureSequence''''' передается индекс корня кучи, с которой начинаем восстановление.
