Изменения

Будем развивать идею пирамидальной сортировки. Для этого будем использовать не [[Двоичная куча|двоичную кучу]], а специальную, полученную с помощью чисел Леонардо<ref>[https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4%D0%BE Википедия {{---}} Числа Леонардо]</ref>, которые задаются следующим образом:

Можно заметить, что куча Леонардо очень похожа на Биномиальную[[Биномиальная куча|биномиальную]]. Куча Леонардо используется из-за свойства, что у каждой вершины либо два, либо ноль детей.

Сортируемый Будем поддерживать следующий инвариант:* сортируемый массив делится на группу подмассивов. Каждый ,* каждый подмассив представляет собой структуру данных {{---}} куча. Каждая ,* каждая куча имеет размер равный одному из чисел Леонардо. Размеры ,* размеры куч строго убывают слева направо. При ,* при этом не существует двух куч, имеющих одинаковый размер. В дальнейшем эту группу подмассивов будем называть последовательность куч. Будем поддерживать инвариант последовательности: корни ,* значения ключей в корнях деревьев идут в порядке возрастания слева направо, и инвариант куч: * в самих кучах значение в детях меньше либо равно значению в родителе.В дальнейшем эту группу подмассивов будем называть последовательность куч.