403
правки
Изменения
Нет описания правки
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за то время <tex>O(1)</tex>.
== Потенциал ==
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> mark[x] == true </tex>). На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.
== Операции ==
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>decreaseKey</tex> и <tex>delete</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.
== Потенциал =makeHeap === Создается новый пустой корневой список, в <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>.
== Извлечение минимума = extractMin ===
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate consolidate </tex>.
=== "Уплотнение" (Consolidate) = consolidate ====
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.
На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) = O(D[H]) </tex> действий.
== Уменьшение ключа = decreaseKey ===
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня; тогда дерево не придется сильно перестраивать. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.
=== Вырезание вершины = cut ====
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> degree[p[x]] </tex>) и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).
=== Каскадное вырезание = cascadingCut ====
[[File:Cascading-cut.png|thumb|600px|Каскадное вырезание]]
На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.
== Удаление вершины = delete ===
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D[H]) = O(D[H]) </tex>.
