Изменения

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

Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark == false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>cut</tex> для текущей вершины и запускаем каскадное вырезание от родителя.

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

На языке метода предоплаты: пусть у каждого узла в списке корней лежит монета, а у каждой помеченной вершины {{---}} 2 монеты. Покажем, что взяв 4 монеты за операцию <tex> decreaseKey </tex>, мы сможем оплатить эту операцию. Одну монету потратим на перенос в корневой список и релаксацию минимума, еще 1 {{---}} на то, чтобы положить монету у новой вершины в корневом списке, которую мы потратим на следующую операцию <tex>extractMin</tex>. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> x.p.mark == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.