212
правок
Изменения
м
→Основная идея
}}
Можно заметить, что куча Леонардо очень похожа на Биномиальную кучу. Куча Леонардо используется из-за свойства, что у каждой вершины либо два, либо ноль детей.
[[Файл:leonardo-heap.png|600px|thumb|right|Пример последовательности куч (список хранит номера чисел Леонардо, соответствующих размерам куч)]]
Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных {{---}} куча. Каждая куча имеет размер равный одному из чисел Леонардо. Размеры куч строго убывают слева направо. При этом не существует двух куч, имеющих одинаковый размер. В дальнейшем эту группу подмассивов будем называть последовательность куч. Будем поддерживать инвариант последовательности: корни деревьев идут в порядке возрастания слева направо, и инвариант куч: значение в детях меньше либо равно значению в родителе.
===Алгоритм:===
'''Шаг 0:''' В массиве записаны элементы, которые надо отсортировать.
'''Шаг 1:''' Превращение массива в последовательность куч.
'''Шаг 2:''' Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
