Фибоначчиева куча

Фибоначчиевы деревья

Определение:

Фибоначчиево дерево - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.

Лемма:

Фибоначчиево дерево ранга [math] k [/math] содержит не менее [math] F_k [/math] ([math] k [/math] число Фибоначчи) вершин

Доказательство:

[math]\triangleright[/math]

Для рангов 0 и 1 соответствующие деревья содержат 1 вершину, [math] F_0 \ge 1, F_1 \ge 1 [/math]. Рассмотрим дерево ранга [math] k [/math] Оно в худшем случае (удален ребенок ранка [math] k - 1 [/math]) содержит [math] 1 + F_1 + F_2 + ... + F_{k-2} [/math] вершин. Эта сумма, в свою очередь, равна [math] F_k [/math]

[math]\triangleleft[/math]

Поскольку [math] F_k = \Omega(\varphi^k) [/math], где [math] \varphi = \frac {1 + \sqrt 5}2 [/math], то высота фибоначчиева дерева есть [math] O(logN) [/math].

Каждая вершина [math] x [/math] знает своего родителя ([math] p[x] [/math]) и какого-нибудь своего ребенка([math] child[x] [/math]).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за [math] O(1) [/math]

Также в любой вершине хранятся поля [math] degree[x], \, mark[x] [/math]: степень вершины(число ее детей) и пометка о том, потеряла ли вершина [math] x [/math] ребенка после того, как она в последний раз сделалась чьим-либо потомком.

Фибоначчиевы кучи

Определение:

Фибоначчиева куча - набор фибоначчиевых деревьев.

Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list).

Доступ к куче осуществляется с помощью указателя [math] min[H] [/math], указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью амортизационного анализа.