Изменения

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

Докажем, что амортизированное время работы операции "уменьшение ключа" <tex>decreaseKey</tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

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

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

Иначе, <tex> mark[p[x]] == true </tex> и там лежит добавляем к помеченной вершине родителя еще 2 монеты. 2 + 2 = В итоге, в родительском узле становится 4монеты, и мы можем рекурсивно продолжить данный процесс. Оценка доказана. На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.