是否有标准的Java实现Fibonacci堆？

Question

我正在研究不同种类的堆数据结构。

斐波那契堆似乎具有更好的最坏时间复杂度，可用于 (1) 插入、(2) 删除和 (3) 查找最小元素的操作。

我在 Java 中发现了一个名为 PriorityQueue 的类，它是平衡二叉堆。但为什么他们没有使用斐波那契堆呢？

此外，在 java.util 中是否有斐波那契堆的实现呢？

谢谢！

- Phil

---

Java集合只提供最常见的数据结构。我认为斐波那契堆更加专业化，或者它可能使用更多的内存。 - Denis Tulskiy

@James，这与斐波那契堆有什么关系呢？o.o - ignis

https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/FibonacciMinPQ.html - maplemaple

Answer 1

不，标准Java集合API中没有Fibonacci堆的实现。我不确定原因是什么，但我认为这是因为虽然在摊还意义下Fibonacci堆是渐进优秀的，但在实践中有巨大的常数因子。集合框架也没有二项式堆，这也是另一个应该包括的好堆。

作为完全无耻的自荐，我在个人网站上有一份用Java编写的Fibonacci堆实现。我不确定它有多少用处，但如果你想看看它是如何工作的，我认为这可能是一个很好的起点。

希望这可以帮助！

- templatetypedef

---

非常感谢。你的实现看起来做得很好，文档也很详细，有很多解释。我会仔细研究一下。 - Phil

哇，我本来是想为了好玩自己写一个的，但你的实现太好了！ - Andy

在实际情况下它的表现如何？斐波那契堆似乎有相当多的内存开销。 - Has QUIT--Anony-Mousse

@Anony-Mousse 斐波那契堆因为你提到的原因在实践中出奇的慢。 - templatetypedef

Answer 2

为什么他们没有使用斐波那契堆？

可能是因为这些堆每个条目的开销比二进制键高得多。

此外，Java.util中是否有斐波那契堆的实现？

没有，但是

3. 有一个来自 Nathan Fiedler 的 graphmaker - 使用 GPL 许可证且具有良好的 测试覆盖率，但是请看一下关于它以及斐波那契实现可能存在的问题的 这篇不错的博客文章。在这篇文章中引用了许多其他 Java 实现。
4. 这里有一些带有单元测试的代码 点击此处
5. JGraphT 项目（也是 Nathan Fiedler）同样具有（一些较小的）测试但使用 LGPL 许可证。
6. 最后还有 Neo4j- 使用 GPL 许可证，没有测试。

- Karussell

Answer 3

为什么他们没有使用斐波那契堆？

我认为主要原因是因为斐波那契堆只有在您有更多 decreaseKey 操作与一个 extractMin 操作相关联的情况下才能帮助。例如，当您将其与 Dijkstra 算法一起使用时。

此外，在 Java.util 中没有实现 Fibonacci 堆，但我对这个话题进行了一些实验，使用了现有的开源版本的 Fibonacci 堆。您可以在我的博客或项目的 GitHub 存储库中找到它。

- gabormakrai

---

请您详细说明一下您对第一个问题的回答。 - arunmoezhi

当然可以。斐波那契堆在执行 decreaseKey 和 insert 操作时比二叉堆更具优势，同时对于 extractMin 操作，它们具有相同的时间复杂度，但是对于 FH 而言，这个操作需要比 BH 更长的时间，因为它正在合并内部树林。因此，如果您只有很少的 decreaseKey，则它比普通的二叉堆慢。对于某些特殊的图形，例如 Dijkstra 算法，就是这种情况。 - gabormakrai