我正在研究Prim算法。代码中有一部分穿过切割的下一个顶点将进入属于MST。在这样做的同时，我们还必须“更新另一组中与离开顶点相邻的所有顶点”。这是来自的快照CLRS:
有趣的部分在于第 1 行。 11. 但由于我们在这里使用堆，因此我们只能访问最小元素，对吧（heap[0]）？那么，即使它们不是最小的顶点，我们如何从堆中搜索和更新顶点，从而除了通过线性搜索之外我们知道它们在哪里？
可以构建支持称为的操作的优先级队列减少键，它获取优先级队列中现有对象的优先级并降低它。现有库附带的大多数版本的优先级队列不支持此操作，但可以通过多种方式构建它。
例如，给定一个二叉堆，您可以维护一个辅助数据结构，将元素映射到它们在二叉堆中的位置。然后，您将更新二进制堆实现，以便每当执行交换时，都会更新此辅助数据结构。然后，要实现减少键，您可以访问该表，找到该节点在二叉堆中的位置，然后继续冒泡步骤。
其他基于指针的堆（例如二项式堆或斐波那契堆）明确支持此操作（斐波那契堆是专门为此设计的）。您通常有一个从对象到它们在堆中占据的节点的辅助映射，然后可以重新连接指针以在堆中移动节点。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
