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> дополнительной памяти.
===Вставка элемента===
