我正在研究不同类型的堆数据结构。
对于 (1) 插入、(2) 删除和 (2) 查找最小元素，斐波那契堆似乎具有更好的最坏情况复杂性。
我发现在 Java 中有一个类PriorityQueue是平衡的二进制堆。但是为什么他们不使用斐波那契堆呢？
另外，是否有斐波那契堆的实现java.util？
谢谢！
问问题
26049 次
3 回答
53
不，标准 Java 集合 API 不包含斐波那契堆的实现。我不确定为什么会这样，但我相信这是因为虽然斐波那契堆在摊销意义上是渐近的，但在实践中它们具有巨大的常数因子。集合框架也没有二项式堆，这将是另一个很好的堆。
作为一个完全无耻的自插件，我在我的个人网站上有一个用 Java 实现的斐波那契堆。我不确定它会有多大用处，但如果你想知道它是如何工作的，我认为这可能是一个很好的起点。
希望这可以帮助！
于 2011-06-08T03:24:43.310 回答
5
但是为什么他们不使用斐波那契堆呢？
可能是因为这些堆的每个条目的开销比二进制键多得多。
此外，Java.util 中是否有斐波那契堆的实现？
不是，但
- 有来自 Nathan Fiedler - GPL的graphmaker并且具有良好的测试覆盖率，但是请查看这篇关于它的不错的博客文章以及斐波那契 impl 可能遇到的问题。在这篇文章中，引用了许多其他 Java 实现。
- 这里有一些带有单元测试的代码
- JGraphT项目（也是 Nathan Fiedler）以及（一些次要的）测试，但 LGPL。
- 最后但并非最不重要的是Neo4j - GPL - 没有测试。
于 2012-01-15T15:15:15.200 回答
1
但是为什么他们不使用斐波那契堆呢？
我认为主要原因是因为斐波那契堆只能在您有更多的 reduceKey 操作连接到一个 extractMin 操作的情况下提供帮助。例如，当您将它与 Dijkstra 算法一起使用时。
此外，Java.util 中是否有斐波那契堆的实现？
Java.util 中没有实现，但我使用现有的开源版本的斐波那契堆对此主题进行了一些实验。您可以在我的博客或项目的 GitHub 存储库上找到它。
于 2015-02-12T18:56:10.010 回答