212
правок
Изменения
→Основная идея
\begin{cases}
1 & \mathrm{if } n = 0, \\
1 & \mathrm{if }n = 1, \\ L(n-1)+L(n-2)+1 & \mathrm{if }n > 1. \\
\end{cases}
</tex>
{{Утверждение
|statement= Любое натуральное число можно представить суммой из <tex dpi = 120> O(\log{N}) </tex> различных чисел Леонардо.
}}
{{Утверждение
|statement= <tex dpi = 120> L(n) = 2 \cdot F(n + 1) - 1 </tex>, где <tex dpi = 120> F(n + 1) </tex> {{---}} <tex dpi 120> (n + 1) </tex>-ое число Фибоначчи.
|proof= Это утверждение доказывается по индукции. База: <tex dpi =120> L(0) = 2 \cdot F(1) - 1 = 1 </tex>. Пусть для <tex dpi = 120> n </tex> первых чисел это равенство выполняется. Делаем индуктивный переход: <tex dpi =120> L(n + 1) = L(n) + L(n - 1) + 1 = 2 \cdot F(n + 1) - 1 + 2 \cdot F(n) - 1 + 1 = 2 \cdot F(n + 2) - 1 </tex>. Утверждение доказано.
}}
}}
Можно заметить, что куча Леонардо очень похожа на [[Биномиальная куча|биномиальную]]. Куча Леонардо используется из-за свойства, что у каждой вершины либо два, либо ноль детейсвоих свойств.
[[Файл:leonardo-heap.png|600px|thumb|right|Пример последовательности куч (список хранит номера чисел Леонардо, соответствующих размерам куч)]]
Будем поддерживать следующий инвариант:
