如何使用Fibonacci堆实现Prim的算法？

Fibonacci堆是一个相当复杂的优先级队列，在其所有操作上具有出色的amoritzed渐近行为 - inserted，find-min和reduce-key都在O（1）摊销时间运行，而delete和extract-min在摊销的O中运行（lg n）时间。如果您想要对该主题有一个很好的参考，我强烈建议您阅读CLRS的“算法简介，第2版”并阅读其中的章节。它写得非常好，非常具有说明性。 Fredman和Tarjan的斐波纳契堆原始论文可在线获取，您可能需要查看。它很密集，但对材料进行了很好的处理。 如果你想看到Fibonacci堆和Prim算法的实现，我必须为我自己的实现提供一个无耻的插件： 我实现了Fibonacci堆。 我使用Fibonacci堆实现Prim的算法。 这两个实现中的注释应该很好地描述它们的工作方式;让我知道我能做些什么来澄清！     

Prim的算法选择在已经选择的涡旋组和其余涡旋之间具有最低权重的边缘。 因此，要实现Prim算法，您需要一个最小堆。每次选择边缘时，都会将新涡旋添加到已经选择的涡旋组中，并且其所有相邻边缘都会进入堆中。 然后从堆中再次选择具有最小值的边。 所以我们得到的时间是： 斐波那契： 选择最小边= O（移除最小值的时间）= O（log（E））= O（log（V）） 将边插入堆= O（将项插入堆的时间）= 1 最小堆： 选择最小边= O（从堆中删除最小值的时间）= O（log（E））= O（log（V）） 将边插入堆= O（将项插入堆的时间）= O（log（E））= O（log（V）） （记住E = ~V ^ 2 ...所以log（E）== log（V ^ 2）== 2Log（V）= O（log（V）） 所以，总共你有E插入和V最小选择（它最后是一棵树）。 所以在Min堆中你会得到： O（Vlog（V）+ Elog（V））== O（Elog（V）） 在Fibonacci堆你会得到： O（Vlog（V）+ E）     

几年前我使用Fibonacci堆实现了Dijkstra，问题非常相似。基本上，Fibonacci堆的优点在于它可以找到一组常量运算的最小值;所以这对Prim和Dijkstra来说非常合适，你必须在每一步都执行这个操作。 为什么这很好 使用二项式堆（这是更“标准”的方式）的那些算法的复杂性是O（E * log V），因为 - 粗略地 - 您将尝试每个边缘（E），并且对于它们中的每一个，您将要么添加新顶点到二项式堆（log V）或减少其键（log V），然后必须找到堆的最小值（另一个log V）。 相反，当您使用Fibonacci堆时，在堆中插入顶点或减少其键的成本是恒定的，因此您只有一个O（E）。但删除顶点是O（log V），因此最终将删除每个顶点，为总O（E + V * log V）添加O（V * log V）。 因此，如果您的图形足够密集（例如E >> V），则使用Fibonacci堆比二项式堆更好。 如何 因此，我们的想法是使用Fibonacci堆来存储可从您构建的子树中访问的所有顶点，并通过导致它的最小边的权重进行索引。如果您使用其他数据结构了解实现或Prim的算法，则使用Fibonacci堆并不存在实际困难 - 只需像往常一样使用堆的insert和deletemin方法，并使用decreasekey方法更新顶点当你释放通向它的边缘时。 唯一困难的部分是实现实际的Fibonacci堆。 我不能在这里给你所有的实现细节（这会占用页面），但是当我这样做时，我非常依赖于算法简介（Cormen等）。如果您还没有，但对算法感兴趣，我强烈建议您获得它的副本！它与语言无关，它提供了有关所有标准算法及其证明的详细解释，并且肯定会提高您的知识和使用所有标准的能力，并设计和证明新的标准。此PDF（来自您链接的Wikipedia页面）提供了一些实现细节，但它绝对不像算法简介那样清晰。 我有一个报告和我在写完之后写的一个演示文稿，它解释了一些如何继续（对于Dijkstra - 请参阅伪代码中的Fibonacci堆函数的ppt的结尾）但它全部是法语...而我的代码是在Caml（和法语），所以我不确定这是否有帮助！如果你能理解它的某些内容请放纵，我只是开始编程，所以当时我的编码技巧很差......