如何为Prim的算法更新堆中的元素优先级？

Question

我正在研究Prim的算法.代码中有一个部分,切割的下一个顶点将会到达属于该顶点的顶点集MST.在这样做的同时,我们还必须"更新另一组中与离开顶点相邻的所有顶点".这是来自的快照CLRS:

有趣的部分在于行号.11.但是由于我们在这里使用堆,我们只能访问最小元素right(heap[0])？那么我们如何从堆中搜索和更新顶点,即使它们不是最小的顶点,因此除了线性搜索之外我们知道它们在哪里？

Answer 1

可以构建支持称为reduce-key的操作的优先级队列,该操作将现有对象的优先级置于优先级队列中并降低它.现有库附带的大多数优先级队列版本都不支持此操作,但可以通过多种方式构建它.

例如,给定二进制堆,您可以维护一个辅助数据结构,该结构从元素映射到二进制堆中的位置.然后,您将更新二进制堆实现,以便每次执行交换时,都会更新此辅助数据结构.然后,要实现reduce-key,您可以访问该表,在二进制堆中查找节点的位置,然后继续冒泡步骤.

其他基于指针的堆如二项式堆或Fibonacci堆显式支持此操作(Fibonacci堆是专门为它设计的).您通常有一个从对象到它们在堆中占用的节点的辅助映射,然后可以重新连接指针以在堆中移动节点.

希望这可以帮助!