Изменения
Нет описания правки
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}
Фибоначчиевы кучи являются сливаемыми(mergeable) кучами.
Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list).
Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.
Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.
= Операции =
== Потенциал ==
Введем потенциал фибоначчиевой кучи <tex> \Phi(H) </tex>, как количество элементов в корневом списке прибавить удвоенное количество вершин с <tex> mark[x] == true </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("уплотнение" кучи).
=== Consolidate ===
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(logN) </tex> вершин.
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке.
