优先级队列中的EXTRACT-MIN操作和DECREASE-KEY操作之间有什么关系？我在使用 Prim 算法的最小跨度问题讲座中遇到了这个问题。
麻省理工学院教授refers to it at point 01:07:16 seconds in the video但我不明白。有人可以帮我解决这个问题吗？
P.S:否则我对优先级队列的理解感到满意。
最佳答案
这个序列:
DECREASE-KEY(node, -infinity)
EXTRACT-MIN
有一个简单的含义:
DELETE-KEY(node)
它的基本作用是确保某个节点到达队列顶部，然后将其删除。
在Prim的算法中，DECREASE-KEY用于更新尚未包含在树中的节点的权重。结果，一个被认为太远的节点现在可能会移动到更接近队列顶部的位置(因此会更快地进行EXTRACT-MIN编辑)。
我现在无法观看视频，但我猜测你的教授的意思是 DECREASE-KEY 增加了节点成为 EXTRACT-MIN 的机会code>ed 并且实际上出于相同的原因使用，因此是一种关系。
关于algorithm - 请解释优先级队列中Decrease-Key和Extract-Min操作之间的关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12624536/