algorithm - 如何用斐波那契堆实现 Prim 算法？

Question

我知道Prim's algorithm我知道它的实现，但我总是跳过我现在想问的部分。据记载，Prim 的算法实现为 Fibonacci heap是 O(E + V log(V)) 并且我的问题是:

• 什么是斐波那契堆？
• 它是如何实现的？和
• 如何使用 Fibonacci 堆实现 Prim 算法？

Answer 1

Fibonacci 堆是一个相当复杂的优先级队列，在其所有操作上都具有出色的平摊渐近行为 - 插入、查找最小值和减少键都在 O(1) 分摊时间内运行，而删除和提取最小值运行在摊销的 O(lg n) 时间内。如果您想获得有关该主题的良好引用，我强烈建议您拿起 CLRS 的“算法导论，第 2 版”副本并阅读其中的章节。它写得非常好并且非常具有说明性。 The original paper on Fibonacci heaps by Fredman and Tarjan可在线获取，您可能想查看一下。它致密，但可以很好地处理 Material 。

如果你想看斐波那契堆和 Prim 算法的实现，我必须为我自己的实现提供一个无耻的插件:

1. My implementation of a Fibonacci heap.
2. My implementation of Prim's algorithm using a Fibonacci heap.

这两个实现中的注释应该很好地描述它们是如何工作的；如果有什么我可以澄清的，请告诉我!