如何更新Prim的算法的堆中的元素优先级？ [英] How to update element priorities in a heap for Prim's Algorithm?

问题描述

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

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

解决方案

可以构建支持称为 reduce-key 的操作的优先级队列，该操作将优先级队列中的现有对象优先级降低。大多数版本的优先级队列随现有库一起提供，不支持此操作，但可以通过多种方式构建它。

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

其他指针像二项式堆或斐波那契堆显示支持这一操作（斐波那契堆是专门设计的）。你通常有一个从对象到它们在堆中占用的节点的辅助映射，然后可以重新连接指针以在堆中移动节点。

希望这有帮助！

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:

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.

Hope this helps!

这篇关于如何更新Prim的算法的堆中的元素优先级？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！