Изменения
→decreaseKey
==== decreaseKey ====
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой [[Список |список]]. Итак, сам алгоритм:
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой [[Список |список]], и производим каскадное вырезание родителя.
===== cut =====
