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

你们有人实现过 斐波那契-堆吗？几年前我就这么做了，但是比起使用基于数组的 BinHeaps，这个数量级慢了好几倍。

当时，我认为这是一个宝贵的教训，说明研究并不总是像它宣称的那样好。然而，许多研究论文声称他们的算法的运行时间基于使用斐波那契堆。

您是否设法生成了一个有效的实现？或者你是否处理过如此庞大的数据集，以至于斐波那契-堆更有效率？如果是这样的话，一些细节将不胜感激。

39918 次浏览
小开
最佳答案

提升 C + + 库包括 boost/pending/fibonacci_heap.hpp中 Fibonacci 堆的实现。这个文件显然已经在 pending/多年，我的预测将永远不会被接受。而且，在这个实现中也存在一些 bug，这些 bug 是我的熟人兼全能酷哥 Aaron Windsor 修复的。不幸的是，我在网上找到的那个文件的大部分版本(以及 Ubuntu 的 libost-dev 包中的那个版本)仍然存在 bug; 我必须从 Subversion 存储库中提取 一个干净的版本。

自从版本 1.49 提升 C + + 库添加了许多新的堆结构，包括 fibonacci 堆。

我能够根据修改后的 Dijkstra 最短路径版本编译 堆性能 cpp来比较 Fibonacci 堆和二进制堆。(在 typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue行中，将 relaxed改为 fibonacci。)我首先忘记使用优化进行编译，在这种情况下，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 堆遭受了巨大的性能打击。

因此，为了从 Fibonacci 堆 在实践中中获益，您必须在减少键的频率非常高的应用程序中使用它们。就 Dijkstra 而言，这意味着底层图是稠密的。一些应用程序可以本质上减少键强度; 我想尝试 Nagomochi-Ibaraki 最小割算法，因为显然它会产生大量的减少键，但它是太多的努力得到一个时间比较工作。

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

理论注释 : Fibonacci 性能的提高使得关键字减少了很多，这对于理论应用很重要，比如 Dijkstra 的运行时。Fibonacci 堆在插入和合并方面也优于二进制堆(Fibonacci 堆的摊销常量时间均为常量时间)。插入本质上是不相关的，因为它不会影响 Dijkstra 的运行时，而且修改二进制堆使插入也包含在摊销的常量时间中是相当容易的。在固定时间内进行合并非常好，但与此应用程序无关。

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

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

小开

Knuth 在1993年为他的书 斯坦福图库做了一个关于最小生成树的斐波那契堆和二进制堆的比较。他发现，在他测试的图形大小(128个不同密度的顶点)中，斐波那契数比二进制堆慢30% 到60% 。

源代码在 MILES _ SPAN 部分的 C 中(或者更确切地说是 CWEB，它是 C、數学和 TeX 之间的交叉)。

小开

免责声明

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

也许我做错了什么，但我 写了一个测试，根据 霸王龙的回答比较:

  • 斐波那契-堆
  • D- 堆(4)
  • 二进制-堆
  • 放松-堆

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

对于输出感到抱歉，它不是很冗长，因为我需要它从文本文件构建一些图表。

以下是结果(以秒为单位) :

heap result table

小开

我还用斐波那契堆做了个小实验。下面是详细信息的链接: 用 dijkstras 算法实验。我刚刚谷歌了术语“ Fibonacci 堆 java”，并尝试了一些现有的 Fibonacci 堆的开源实现。它们中的一些似乎有一些性能问题，但有一些是相当不错的。至少，在我的测试中，它们击败了天真和二进制堆 PQ 的性能。也许他们可以帮助实现有效的方法。


提交答案