Изменения
Нет описания правки
{{Лемма
|statement=
Фибоначчиево дерево ранга с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
|proof=
Для рангов 0 и 1 соответствующие деревья содержат 1 вершинуне менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.
Рассмотрим дерево ранга степени <tex> k </tex>
Оно в худшем случае (удален ребенок ранка <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.
}}
Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то высота фибоначчиева дерева максимальная степень вершины в фибоначчиевой куча с <tex> N </tex> вершинами есть <tex> O(logN) </tex>.
Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).
== Потенциал ==
Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H] ) </tex>, как количество элементов в корневом списке (<tex> t[H] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.
== Make_heap Создание кучи ==
Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.
== Merge Слияние ==
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.
== Insert Вставка элемента ==
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.
== Extract_min Извлечение минимума ==
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.
=== "Уплотнение" (Consolidate ) ===
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H}]) </tex> вершин.
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.
Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:
Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>.
