我在研究普里姆的算法。代码中有一个部分，切割的下一个顶点将到达属于MST的顶点集。这样做的同时，我们还必须“更新另一个集合中与出发顶点相邻的所有顶点”。这是CLRS的快照：
有趣的部分在第11行。但是由于我们在这里使用堆，所以我们只能访问最小的元素，对不对（heap[0]）？因此，我们如何从堆中搜索和更新顶点，即使它们不是最小的，因此我们知道它们在哪里，除了线性搜索？
最佳答案
可以构建支持称为RealKEY的操作的优先级队列，它在优先级队列中采用现有对象的优先级并降低它。与现有库一起使用的大多数优先级队列都不支持此操作，但有可能以多种方式构建它。
例如，给定一个二进制堆，可以维护一个辅助数据结构，该结构可以从元素映射到二进制堆中的位置。然后，您将更新二进制堆实现，以便每当执行交换时，该辅助数据结构被更新。然后，要实现reduce key，可以访问表，找到节点在二进制堆中的位置，然后继续冒泡步骤。
其他基于指针的堆（如二项式堆或斐波那契堆）明确支持此操作（斐波那契堆是专门为其设计的）。通常，从对象到堆中的节点都有一个辅助映射，然后可以重新连接指针，以便在堆中移动节点。
希望这有帮助！