212
правок
Изменения
→Основная идея
{{Определение
|definition =
'''''K-ая куча Леонардо''''' — это двоичное дерево с количеством вершин <tex dpi = 120> L(k)</tex>, удовлетворяющее следующим условиям:
* Число, записанное в корне не меньше чисел в поддеревьях
* Левым поддеревом является <tex dpi = 120> (k-1)</tex>-я куча Леонардо* Правым — <tex dpi = 120> (k-2)</tex>-якуча Леонардо
}}
Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом, элементы этой последовательности будут строго уменьшаться корни деревьев идут в размере с ростом порядкового номерапорядке возрастания слева направо.
При этом не существует двух куч, имеющих одинаковый размер.
Так же никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи.
Если мы будем использовать подряд две кучи размерностью <tex dpi = 120> L(x) </tex> и <tex dpi = 120> L(x+1) </tex>, то их можно будет заменить одной – размерностью <tex dpi = 120> L(x+2) </tex>.
'''Алгоритм представляет из себя несколько стадий:'''
* Конструирование последовательности куч
* Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
