我正在学习Prim的算法.代码中有一部分,剪切中的下一个顶点将来到属于MST的顶点集合.在这样做的时候,我们还必须“更新另一组中与离开顶点相邻的所有顶点”.这是CLRS的快照：
有趣的部分在于行号.但是由于我们在这里使用一个堆,我们只能访问最小元素,右(heap [0])？那么我们如何从堆中搜索和更新顶点,即使它们不是最小的,因此我们知道除了线性搜索之外哪里呢？
解决方法
可以构建支持称为reduce-key的优先级队列,该操作将优先级队列中的现有对象的优先级降低.现有库附带的大多数版本的优先级队列不支持此操作,但可以通过多种方式构建它.
例如,给定一个二进制堆,您可以维护辅助数据结构,从二进制堆中的元素映射到它们的位置.然后,您将更新二进制堆实现,以便每当执行交换时,将更新此辅助数据结构.然后,要实现reduce-key,您可以访问该表,查找二进制堆中节点的位置,然后继续启动一个弹出窗口.
像二叉堆或斐波纳契堆的其他指针式堆显然支持这个操作(斐波纳契堆是专门设计的).通常,从对象到它们在堆中占用的节点有一个辅助映射,然后可以重新连接指针以在堆中移动节点.
希望这可以帮助！
