你们中有没有人实现过Fibonacci-Heap？几年前，我这样做了，但是比使用基于数组的BinHeaps要慢几个数量级。
那时，我认为这是一门宝贵的类(class)，说明研究并不总是如其所声称的那样出色。但是，许多研究论文声称其算法使用的是Fibonacci-Heap技术。
您是否曾经设法产生有效的实现方案？还是您使用的数据集如此之大，以至于斐波那契堆更有效？如果是这样，一些细节将不胜感激。
最佳答案
Boost C++ libraries在boost/pending/fibonacci_heap.hpp中包含Fibonacci堆的实现。该文件显然已经存在pending/多年了，根据我的预测，该文件将永远不会被接受。另外，该实现中也存在一些错误，这些错误是由我和熟人Aaron Windsor所熟识的。不幸的是，我可以在网上找到的那个文件的大多数版本(以及Ubuntu的libboost-dev软件包中的那个)仍然存在bug。我不得不从Subversion存储库中提取a clean version。
从1.49版本开始，Boost C++ libraries添加了许多新的堆结构，包括斐波那契堆。
我能够针对dijkstra_heap_performance.cpp的修改版本编译dijkstra_shortest_paths.hpp，以比较斐波那契堆和二进制堆。 (在typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue行中，将relaxed更改为fibonacci。)我首先忘记进行优化编译，在这种情况下，Fibonacci和二进制堆的性能大致相同，而Fibonacci堆的性能通常可忽略不计。在我进行了非常强大的优化后，二进制堆得到了极大的 push 。在我的测试中，当图非常大且密集时，斐波那契堆的性能仅优于二进制堆，例如:
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;我想尝试the Nagomochi-Ibaraki minimum-cut algorithm，因为它显然会生成很多reduce_keys，但是要使计时比较正常工作需要付出很大的努力。
警告:我可能做错了什么。您不妨尝试自己重现这些结果。
理论注释:Fibonacci堆在reduce_key上的性能提高对于理论应用程序(例如Dijkstra的运行时)很重要。 Fibonacci堆在插入和合并时也胜过二进制堆(Fibonacci堆的均摊固定时间)。插入本质上是无关紧要的，因为它不会影响Dijkstra的运行时，并且修改二进制堆以在摊销的固定时间内插入也相当容易。固定时间合并非常棒，但与该应用程序无关。
个人说明:我的一个 friend 和我曾经写过一篇论文，解释了一个新的优先级队列，该队列试图复制Fibonacci堆的(理论上)运行时间，而没有它们的复杂性。该论文从未发表过，但是我的合著者确实实现了二进制堆，斐波那契堆以及我们自己的优先级队列来比较数据结构。实验结果的图表表明，就总比较而言，斐波那契堆的性能稍好于二进制堆，这表明在比较成本超过开销的情况下，斐波那契堆的性能会更好。不幸的是，我没有可用的代码，大概在您的情况下比较便宜，因此这些注释是相关的，但不直接适用。
顺便提一句，我强烈建议尝试将Fibonacci堆的运行时与您自己的数据结构进行匹配。我发现自己只是重新发明了斐波那契堆。在我以为斐波那契堆的所有复杂性都是一些随机的想法之前，但后来我意识到它们都是自然的并且相当强制。
关于performance - 有人实际上有效地实现了斐波那契堆吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/504823/