我学习Prim算法。还有就是$ C $中的C部分穿过切下一个顶点会来设定属于 MST 顶点。虽然这样做，我们也有'更新另一组与其相邻的出发顶点的所有顶点。这是从快照 CLRS ：

I am studying Prim's Algorithm. There is a part within the code the next vertex across the cut will be coming to the set of the vertices belonging to the MST. While doing that, we also have to 'update all vertices in the other set which are adjacent to the departing vertex'. This is a snapshot from CLRS:

有趣的部分在于行没有。 11.但是，由于我们在这里使用一个堆，我们只能访问最小元素，右（堆[0] ）？那么，我们如何搜索和堆更新顶点，即使他们不是最小的一个，因此，我们也知道他们在哪里，除了通过线性搜索？

The interesting part lies in line no. 11. But since we are using a heap here, we have access to only the minimum element, right (heap[0])? So how do we search and update vertices from the heap even though they are not the minimum one and thus we have knowing where they are except by linear search?

推荐答案

有可能构建支持所谓的操作的优先级队列的减小键的，这需要现有对象的优先级在优先级队列，并降低它。大多数版本的优先级队列附带现有库不支持这种操作，但它可以通过多种方式来构建它。

It is possible to build priority queues that support an operation called decrease-key, which takes the priority of an existing object in a priority queue and lowers it. Most versions of priority queues that ship with existing libraries don't support this operation, but it's possible to build it in several ways.

例如，给定一个二元堆，可以维护一个映​​射，从内容到自己的位置，在二元堆一个辅助的数据结构。然后，将更新的二进制堆实现，以便每当交换进行，该辅助数据结构更新。然后，为了实现减小键，可以访问表，找到在二进制堆的节点的位置，则继续有气泡的向上步

For example, given a binary heap, you can maintain an auxiliary data structure that maps from elements to their positions in the binary heap. You would then update the binary heap implementation so that whenever a swap is performed, this auxiliary data structure is updated. Then, to implement decrease-key, you could access the table, find the position of the node in the binary heap, then continue a bubble-up step.

其它基于指针的堆状二项式堆或斐波那契堆明确支持此操作（斐波那契堆是专门为它设计的）。通常你的对象，他们占据了堆中，然后重新连接指针移动节点在堆周围的节点辅助映射。

Other pointer-based heaps like binomial heaps or Fibonacci heaps explicitly support this operation (the Fibonacci heap was specifically designed for it). You usually have an auxiliary map from objects to the node they occupy in the heap and can then rewire the pointers to move the node around in the heap.

希望这有助于！