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

Question

你们中有谁实现过Fibonacci-Heap吗？我在几年前就这样做了，但它比使用基于数组的BinHeaps慢了几个数量级。

当时，我认为这是一个宝贵的教训，告诉我研究并不总是像它声称的那样好。然而，许多研究论文声称其算法的运行时间是基于Fibonacci-Heap。

你有没有设法实现一个高效的实现？或者，您是否处理过如此大的数据集，以至于Fibonacci-Heap更高效？如果是这样的话，一些细节将不胜感激。

Answer 1

1993年，Knuth在他的书Stanford Graphbase中对斐波那契堆和二进制堆进行了最小生成树的比较。他发现，在他正在测试的图大小下，斐波那契速度比二进制堆慢30%到60%，在不同密度下有128个顶点。

在MILES_SPAN部分中，source code在C中(或者更确切地说是CWEB，它是C、math和TeX的混合体)。

Answer 2

免责声明

我知道结果非常相似，“看起来运行时间完全由堆以外的其他东西控制”(@Alpedar)。但我在代码里找不到任何证据。它的代码是开放的，所以如果你能找到任何可能影响测试结果的东西，请告诉我。

也许我做错了什么，但我wrote a test，根据A.Rex的分析比较：

• Fibonacci-Heap
• D-Ary-heap (4)
• Binary-Heap
• Relaxed-Heap

所有堆的执行时间(仅针对完整图)非常接近。对具有1000、2000、3000、4000、5000、6000、7000和8000个顶点的完全图进行了测试。对于每个测试，生成了50个随机图，输出是每个堆的平均时间：

抱歉，输出不是很详细，因为我需要它来从文本文件构建一些图表。

结果如下(以秒为单位)：

​

​

Answer 3

我还用斐波那契堆做了一个小实验。以下是详细信息的链接：Experimenting-with-dijkstras-algorithm。我只是在谷歌上搜索了"Fibonacci heap java“，并尝试了一些现有的斐波那契堆的开源实现。它们中的一些似乎有一些性能问题，但也有一些是相当不错的。至少，在我的测试中，它们击败了naive和二进制堆PQ的性能。也许他们可以帮助实现有效的方法。