有没有人真正有效地实现了斐波那契堆？

由于版本 1.49 Boost C++ libraries 添加了许多新的堆结构，包括斐波那契堆。

我能够针对 dijkstra_shortest_paths.hpp 的修改版本编译 dijkstra_heap_performance.cpp 以比较斐波那契堆和二进制堆。 （在第 typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue 行中，将 relaxed 更改为 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.

据我了解，这涉及到斐波那契堆和二进制堆之间的根本区别。两种数据结构之间唯一真正的理论区别是斐波那契堆在（摊销的）恒定时间内支持递减键。另一方面，二叉堆从它们作为数组的实现中获得了很大的性能。使用显式指针结构意味着斐波那契堆会遭受巨大的性能打击。

因此，在实践中要从斐波那契堆中受益，您必须在 reduce_key 异常频繁的应用程序中使用它们。就 Dijkstra 而言，这意味着底层图是密集的。一些应用程序可能本质上是减少键强度；我想尝试 the Nagomochi-Ibaraki minimum-cut algorithm，因为它显然会生成很多 reduce_keys，但要让时间比较工作起来太费劲了。

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

理论说明：在 reduction_key 上改进的斐波那契堆性能对于理论应用很重要，例如 Dijkstra 的运行时。斐波那契堆在插入和合并方面也优于二叉堆（斐波那契堆的摊销常数时间）。插入本质上是无关紧要的，因为它不会影响 Dijkstra 的运行时，并且修改二进制堆以在摊销的常数时间内也具有插入是相当容易的。在恒定时间内合并非常棒，但与此应用程序无关。

个人笔记：我和我的一个朋友曾经写过一篇论文，解释了一个新的优先级队列，它试图在没有复杂性的情况下复制斐波那契堆的（理论）运行时间。这篇论文从未发表过，但我的合著者确实实现了二进制堆、斐波那契堆和我们自己的优先级队列来比较数据结构。实验结果的图表表明，斐波那契堆在总比较方面略胜二叉堆，这表明斐波那契堆在比较成本超过开销的情况下表现更好。不幸的是，我没有可用的代码，并且可能在您的情况下比较便宜，所以这些评论是相关的，但不直接适用。

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