Изменения

С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>ExtractMinextractMin</tex> и <tex>Deletedelete</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].

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

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи)<tex> consolidate </tex>. Возьмем указатель на <tex> H.min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] (n) </tex>, где <tex> D[H] (n) </tex> {{---}} максимальная степень вершины в куче) все положим в корневой списокобъединим с корневым списком. Теперь вызываем процедуру <tex> consolidate </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>extraxtMin</tex>, учитывая и вспомогательную функцию <tex> consolidate </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. Но по доказанной выше [[#Лемма4|лемме]] это <tex>O(\log(n))</tex>.

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой не более <tex> OD(D[H]n) </tex> вершин.

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

Учетная стоимость <tex> Consolidate consolidate </tex> равна <tex> O(D[H](n)) </tex>. Докажем это:

Пусть изначально Изначально в корневом списке было не более <tex> r D(n) + t[H] - 1 </tex> вершин. Тогда в ходе операции , поскольку он состоит из исходного списка корней с <tex> Consolidate t[H]</tex> мы сделали узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> OD(rn) </tex> слияний деревьев. Но эти В ходе операции <tex> O(r) consolidate </tex> слияний скомпенсируются уменьшением потенциала мы сделали <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H](n) - r) = O(D+ t[H]) </tex>слияний деревьев. Остальных действий будет также Потенциал перед извлечением минимума равен <tex> O(Dt[H] + 2m[H]) </tex>. Таким образом, учетная стоимость а после не превышает <tex> Consolidate: \, OD(Dn) + 1 + 2m[H]</tex>, поскольку в корневом списке остается не более <tex> D(n) + 1 </tex>узлов, а количество помеченных узлов не изменяется.Таким образом, амортизированная стоимость не превосходит

На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D(n) + t[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O+ (D(n) + 1 + 2m[H]) - (t[H] + O(D2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex> Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex> действий.