所述 升压C
++库包括斐波那契堆在一个实现boost/pending/fibonacci_heap.hpp。该文件显然已经存在pending/多年，根据我的预测，该文件将永远不会被接受。另外，该实现中也存在一些错误，这些错误是由我和熟人Aaron
Windsor所熟识的。不幸的是，我可以在网上找到的那个文件的大多数版本（以及Ubuntu的libboost-
dev软件包中的那个）仍然存在bug。我不得不从Subversion存储库中提取一个干净的版本。

从1.49 版开始，Boost C
++库添加了许多新的堆结构，包括斐波那契堆。

我能够编译dijkstra_heap_performance.cpp对修改后的版本dijkstra_shortest_paths.hpp比较斐波那契堆和二进制堆。（在该行中typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue，更改relaxed为fibonacci。）我首先忘记进行优化编译，在这种情况下，Fibonacci和二进制堆的性能大致相同，而Fibonacci堆的性能通常可忽略不计。经过非常强大的优化编译后，二进制堆得到了极大的提升。在我的测试中，当图非常大且密集时，斐波那契堆的性能仅优于二进制堆，例如：

Generating graph...10000 vertices, 20000000 edges.
Running Dijkstra's with binary heap...1.46 seconds.
Running Dijkstra's with Fibonacci heap...1.31 seconds.
Speedup = 1.1145.

据我了解，这涉及到斐波纳契堆和二进制堆之间的根本区别。两种数据结构之间唯一真正的理论差异是，斐波那契堆在（摊销后的）恒定时间内支持减少密钥。另一方面，二进制堆通过以数组的形式实现而获得了很多性能。使用显式指针结构意味着斐波那契堆遭受巨大的性能损失。

因此，要从 实践中
受益于Fibonacci堆，您必须在reduce_keys非常频繁的应用程序中使用它们。用Dijkstra来说，这意味着基础图是密集的。某些应用程序可能本质上是reduce_key-
intense; 我想尝试一下Nagomochi-
Ibaraki最小限度算法，因为它显然会生成很多reduce_keys，但是要进行时序比较工作需要付出很大的努力。

警告 ：我可能做错了什么。您不妨尝试自己重现这些结果。

理论注释
：Fibonacci堆在reduce_key上的性能提高对于理论应用程序（例如Dijkstra的运行时）很重要。Fibonacci堆在插入和合并时也胜过二进制堆（Fibonacci堆的均摊固定时间）。插入本质上是无关紧要的，因为它不会影响Dijkstra的运行时，并且修改二进制堆以在固定的固定时间内插入也很容易。固定时间合并非常好，但与该应用程序无关。

个人说明
：我的一个朋友和我曾经写过一篇论文，解释了一个新的优先级队列，该队列试图在没有复杂性的情况下复制Fibonacci堆的（理论上）运行时间。该论文从未发表过，但是我的合著者确实实现了二进制堆，斐波那契堆以及我们自己的优先级队列来比较数据结构。实验结果的图表表明，就总比较而言，斐波那契堆的性能稍好于二进制堆，这表明在比较成本超过开销的情况下，斐波那契堆的性能会更好。不幸的是，我没有可用的代码，大概在您的情况下比较便宜，因此这些注释是相关的，但不直接适用。

顺便提一句，我强烈建议尝试将Fibonacci堆的运行时与您自己的数据结构进行匹配。我发现自己只是重新发明了斐波那契堆。在我以为斐波那契堆的所有复杂性都是一些随机的想法之前，但后来我意识到它们都是自然的并且相当强迫。