Изменения

При конструировании последовательности куч будем последовательно выполнять вставку в конец новых элементов. В итоге мы получим, что наш массив разбит на подмассивы размером <tex dpi = 120> L(k) </tex>. Для каждого подмассива выполним операцию '''heapify'''(она выполняется так же, как в [[Двоичная куча|двоичной куче]]), после которой необходимо будет отсортировать корни куч, чтобы выполнялся инвариант последовательности. Следовательно, нам необходимы две четыре операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого размера) и , уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности, операция сортировки корней куч и восстановление инварианта последовательности.

Для сортировки корней будем использовать [[Сортировка пузырькомвыбором|сортировку пузырькомвыбором]]. Пусть в последовательности <tex dpi = 120> l = O(\log{N}) </tex>куч. Сортировать будем с конца, то есть в начале текущей назначается последняя куча. Тогда после первой итерации в самой правой куче мы получим максимальный корень. А кучу, из которой этот корень пришел в текущую, после обмена корнем необходимо просеять. А затем уменьшаем <tex dpi = 120> l </tex> на <tex dpi =120> 1 </tex>. Повторяем эти действия, пока <tex dpi = 120> l </tex> не станет равна <tex dpi =120> 1 </tex>. Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то сортировка вставками работает за <tex dpi =120> O(\log^2{N}) </tex>. Просеивание выполняется за <tex dpi =120> O(\log{N}) </tex>, то в итоге алгоритм работает за <tex dpi =120> O(\log^2{N}) + O(\log{N}) \cdot O(\log{N}) = O(\log^2{N})</tex>