3622
правки
Изменения
м
→Основная идея
|definition =
'''''K-ая куча Леонардо''''' — это двоичное дерево с количеством вершин <tex dpi = 120> L(k) </tex>, удовлетворяющее следующим условиям:
* число, записанное в корне , не меньше чисел в поддеревьях,
* левым поддеревом является <tex dpi = 120> (k-1) </tex>-я куча Леонардо,
* правым — <tex dpi = 120> (k-2) </tex>-я куча Леонардо.
}}
Можно заметить, что куча Леонардо очень похожа на [[Биномиальная куча|биномиальную]]. Куча Леонардо используется из-за своих свойств.
[[Файл:leonardo-heap.png|600px|thumb|right|Пример последовательности куч (список хранит номера чисел Леонардо, соответствующих размерам куч)]]
Будем поддерживать следующий инвариант:
