有没有人实际上实现了Fibonacci-Heap？
有没有人实施过斐波纳契堆 ？ 我几年前就这样做了，但比使用基于arrays的BinHeaps慢了几个数量级。
那时候，我认为这是一个很有价值的教训，就是研究并不总是像自称的那么好。 然而，很多研究论文都是基于使用Fibonacci-Heapalgorithm的运算时间。
你有没有设法产生一个有效的实施？ 还是你使用的数据集太大，斐波那契堆更有效率？ 如果是这样，一些细节将不胜感激。
Boost C ++库包含 boost/pending/fibonacci_heap.hpp的Fibonacci堆的实现。这个文件显然是在 pending/多年，我的预测将永远不会被接受。另外，这个实施中也存在一些问题，这些问题是由我的熟人和全能冷静的亚伦·温莎（Aaron Windsor）所确定的。 不幸的是，我能find的那个文件的大部分版本（以及Ubuntu的libboost-dev软件包中的那个版本）仍然存在缺陷; 我不得不从Subversion版本库中取出一个干净的版本 。
自1.49版本以来， Boost C ++库增加了许多新的堆结构，包括斐波那契堆。
我能够针对dijkstra_shortest_paths.hpp的修改版本编译dijkstra_heap_performance.cpp来比较斐波那契堆和二进制堆。 （在行的typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue ，改为relaxed到fibonacci 。）我首先忘了编译优化，在这种情况下斐波那契和二进制堆执行大致相同，斐波那契堆通常优于一个微不足道的数量。 在我编写了非常强大的优化之后，二进制堆得到了巨大的提升。 在我的testing中，斐波那契堆只在图表非常大而且密集时才超过二进制堆，例如：
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.
据我所知，这涉及到斐波那契堆和二进制堆之间的根本区别。 两个数据结构之间唯一真正的理论差异是斐波那契堆支持（摊还）恒定时间的减less键。 另一方面，二进制堆从数组的实现中获得了很大的性能， 使用明确的指针结构意味着斐波那契堆受到巨大的性能影响。
因此， 在实践中受益于斐波那契堆，您必须在reduce_keys非常频繁的应用程序中使用它们。 就Dijkstra而言，这意味着底层图很密集。 某些应用程序本质上可能会降低密钥强度; 我想尝试Nagomochi-Ibaraki最小切割algorithm，因为它显然会产生大量的reduce_keys ，但是要花费很多精力来进行时序比较。
警告 ：我可能做错了什么。 你可能希望自己尝试重现这些结果。
理论笔记 ：斐波那契数组在reduce_key上的改进性能对理论应用（例如Dijkstra的运行时）非常重要。 斐波那契堆在插入和合并方面也performance优于二进制堆（这两个堆均为斐波那契堆的恒定时间）。 插入本质上是不相关的，因为它不影响Dijkstra的运行时间，并且修改二进制堆相当容易，也可以在分期固定的时间内插入插入。 在不断的时间合并是太棒了，但与这个应用程序无关。
个人说明 ：我的一位朋友和我曾经写过一篇论文，解释一个新的优先级队列，试图复制斐波那契堆的（理论）运行时间，而不复杂。 该论文从未发表，但我的合着者实现了二进制堆，斐波那契堆和我们自己的优先级队列来比较数据结构。 实验结果的图表表明斐波那契堆在整体比较方面performance略逊于二进制堆，表明斐波那契堆在比较成本超过开销的情况下performance更好。 不幸的是，我没有可用的代码，大概在你的情况比较便宜，所以这些评论是相关的，但不直接适用。
顺便提一句，我强烈build议试图将斐波纳契堆的运行时间与您自己的数据结构进行匹配。 我发现我自己改造了斐波纳契堆。 在我想到斐波那契堆的所有复杂性都是一些随机的想法之前，我才意识到它们都是自然而且被迫的。
Knuth在他的书“ 斯坦福图像库 ”（ Stanford Graphbase）中做了一个关于斐波那契堆和二叉堆的最小生成树的比较 。 他发现斐波那契在他testing的graphics大小上比二进制堆慢30到60个百分点，不同密度的128个顶点。
在MILES_SPAN部分中， 源代码是C（或者说CWEB，它是C，math和TeX之间的交叉）。
放弃
我知道结果是非常相似的，“看起来运行时间完全由除堆以外的东西支配”（@Alpedar）。 但是我在代码中找不到任何证据。 它的代码是开放的，所以如果你能find任何可能影响testing结果的东西，请告诉我。
也许我做错了，但我写了一个testing ，基于A.Rex anwser比较：
- 斐波那契堆
- D-Ary-堆（4）
- 二进制堆
- 宽松堆
所有堆的执行时间（仅适用于完整图）非常接近。 对1000,2000,3000,4000,5000,6000,7000和8000个顶点的完整图进行了testing。 对于每个testing，生成50个随机图并且输出是每个堆的平均时间：
对输出抱歉，这不是很详细，因为我需要它从文本文件build立一些图表。
以下是结果（以秒为单位）：
我也做了一个斐波那契堆的小实验。 这里是详细的链接： 与dijkstrasalgorithm实验 。 我刚刚search了术语“Fibonacci堆Java”，并尝试了一些现有的开源实现的斐波那契堆。 看来他们中的一些人有一些performance问题，但也有一些是相当不错的。 至less，他们打败了我的testing中的天真和二进制堆PQ性能。 也许他们可以帮助实施高效率的。
