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

发布时间：2020-12-14 16:45:12 所属栏目：Java 来源：网络整理

导读：我正在学习Prim的算法.代码中有一部分,剪切中的下一个顶点将来到属于MST的顶点集合.在这样做的时候,我们还必须“更新另一组中与离开顶点相邻的所有顶点”.这是CLRS的快照：有趣的部分在于行号.但是由于我们在这里使用一个堆,我们只能访问最小元素,右(heap [

我正在学习Prim的算法.代码中有一部分,剪切中的下一个顶点将来到属于MST的顶点集合.在这样做的时候,我们还必须“更新另一组中与离开顶点相邻的所有顶点”.这是CLRS的快照：

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

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

例如,给定一个二进制堆,您可以维护辅助数据结构,从二进制堆中的元素映射到它们的位置.然后,您将更新二进制堆实现,以便每当执行交换时,将更新此辅助数据结构.然后,要实现reduce-key,您可以访问该表,查找二进制堆中节点的位置,然后继续启动一个弹出窗口.

像二叉堆或斐波纳契堆的其他指针式堆显然支持这个操作(斐波纳契堆是专门设计的).通常,从对象到它们在堆中占用的节点有一个辅助映射,然后可以重新连接指针以在堆中移动节点.

希望这可以帮助！

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!