Изменения

Фибоначчиево дерево с вершиной степени <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>

Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(logN\log N) </tex>. Обозначим эту величину за <tex> D[H] </tex>.

Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, где <tex> t[H] </tex> {{- --}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{--- }} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> mark[x] == true </tex>). Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{- --}} <tex> O(1) </tex>.

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{- --}} <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> {{- --}} максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.

Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{- --}} максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.

Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]] : добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.

[[File:Cascading-cut.png|thumb|450px600px|Каскадное вырезание]]

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2 * k 2k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>. Теперь также стало ясно, для чего в определении нашего потенциала количество вершин с пометкой <tex> mark[x] </tex> учитывается вдвое больше, чем количество вершин в корневом списке.