Изменения
Нет описания правки
'''Фибоначчиевы кучи''' - модификация биномиальных куч, в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.
= Фибоначчиевы деревья =
{{Определение
}}
Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.
== Потенциал ==
Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = t[H] + 2m[H] </tex>, как количество элементов в корневом списке (<tex> t[H] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.
== Make_heap ==
== Merge ==
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются и , итоговая сумма потенциалов не изменяютсяизменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.
== Insert ==
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(logN) </tex> вершин.
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке.<tex> D[H] = O(logN) </tex>. Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex> Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку. Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:
