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

Question

我正在研究不同类型的堆数据结构.

Fibonacci堆似乎具有更好的最坏情况复杂度(1)插入,(2)删除和(2)找到最小元素.

我发现在Java中有一个类PriorityQueue是平衡的二进制堆.但为什么他们不使用Fibonacci堆？

另外,是否有斐波那契堆的实现java.util？

谢谢!

Answer 1

不,标准Java集合API不包含Fibonacci堆的实现.我不确定为什么会这样,但我相信这是因为虽然斐波那契堆在分摊意义上是渐近的,但它们在实践中有很大的常数因素.集合框架也没有二进制堆,这将是另一个要包含的好堆.

作为一个完全无耻的自我插件,我在我的个人网站上用Java实现了Fibonacci堆.我不确定它会有多大用处,但是如果你很想知道它是如何工作的,我认为它可能是一个很好的起点.

希望这可以帮助!

Answer 2

但为什么他们不使用Fibonacci堆？

可能是因为那些堆每个条目的开销比二进制密钥多得多.

另外,Java.util中是否有Fibonacci堆的实现？

不是,但

3. 有来自Nathan Fiedler-GPL的图形制作者,并且具有良好的测试覆盖率,但是看看这篇关于它的博客文章以及斐波纳契impl可能存在的问题.在这篇文章中,引用了许多其他Java实现.
4. 有一些代码单元测试在这里
5. 该JGraphT项目(也弥敦道费德勒),也有(一些小的)的测试,但LGPL.
6. 最后但并非最不重要的是Neo4j - GPL - 没有测试.