Какая связь между операцией EXTRACT-MIN и операциями DECREASE-KEY в приоритетной очереди? Я столкнулся с этим в лекции по проблеме минимального охвата с использованием алгоритма Прима.
Профессор из Массачусетского технологического института ссылается на это в точке 01:07:16 секунды видео, но я не понимаю . Может ли кто-нибудь прояснить это для меня?
P.S. Меня устраивает мое понимание приоритетных очередей.
Эта последовательность:
DECREASE-KEY(node, -infinity)
EXTRACT-MIN
Имеет простое значение:
DELETE-KEY(node)
Что он в основном делает, так это убеждается, что определенный узел попадает в начало очереди, а затем удаляет его.
В алгоритме Прима DECREASE-KEY используется для обновления веса узлов, еще не включенных в дерево. В результате узел, который считался слишком далеко, теперь может переместиться ближе к началу очереди (и, следовательно, будет EXTRACT-MINed раньше).
Я не могу просмотреть видео прямо сейчас, но я предполагаю, что ваш профессор имел в виду, что DECREASE-KEY увеличивает шансы узла быть EXTRACT-MINed и фактически используется по той же причине и, следовательно, своего рода отношения.
