Изменения
Нет описания правки
{{Лемма
|statement=
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> (вершин, где <tex> F_k </tex> - <tex> k </tex> число Фибоначчи) вершин, определяемое формулой: <tex> F_0 = F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} </tex>
|proof=
Для вершин со степенью 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.
Рассмотрим дерево степени <tex> k </tex>
Оно в худшем случае (удален ребенок ранка со степенью <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... \dots + F_{k-2} </tex> вершин.
Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}
[[File:Fibonacci-heap.png|thumb|273px400px|Пример фибоначчиевой кучи]]
Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.
Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.
== Потенциал ==
Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, как где <tex> t[H] </tex> - количество элементов в корневом списке (кучи, а <tex> tm[H] </tex>) прибавить удвоенное - количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> mark[x] == true \, (m[H]) </tex>). Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.
== Создание кучи ==
== Извлечение минимума ==
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.
=== "Уплотнение" (Consolidate) ===
Пусть изначально в корневом списке было <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>.
На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) = O(D[H]) </tex> действий.
== Уменьшение ключа ==
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. ХотимБыло бы хорошо, чтобы вершина не всплывала до корня; тогда дерево не придется сильно перестраивать. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:
# Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
=== Вырезание вершины ===
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> degree[p[x]] </tex> ) и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).
=== Каскадное вырезание ===
[[File:Cascading-cut.png|thumb|273px450px|Каскадное вырезание]]
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.
