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