algorithm - 请解释优先级队列中的Decrease-Key和Extract-Min操作之间的关系

Question

优先级队列中的EXTRACT-MIN操作和操作之间的关系是什么？DECREASE-KEY我在使用 Prim 算法的最小跨度问题的讲座中遇到了这个问题。

麻省理工学院的教授在视频中的 01:07:16 秒时提到了它，但我不明白。有人可以帮我解决这个问题吗？

PS：否则我对我对优先队列的理解感到满意。

Answer 1

这个序列：

DECREASE-KEY(node, -infinity)
EXTRACT-MIN

有一个简单的含义：

DELETE-KEY(node)

它的基本作用是确保某个节点到达队列的顶部，然后将其删除。

在 Prim 算法中，DECREASE-KEY用于更新尚未包含在树中的节点的权重。结果，一个被认为太远的节点现在可能会更靠近队列的顶部（因此会EXTRACT-MIN更快地被编辑）。

我现在无法观看视频，但我的猜测是您的教授的意思是DECREASE-KEY增加了节点被EXTRACT-MIN编辑的机会，并且实际上出于相同的原因使用，因此是一种关系。