是否有一个标准的Java实现的斐波纳契堆？ [英] Is there a standard Java implementation of a Fibonacci heap?

问题描述

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

斐波纳契堆似乎对（1）插入，（2）删除和（2）找到最小元素有更好的最坏情况复杂度。

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

另外，在 java.util ？

谢谢！

解决方案

不，标准Java集合API不包含Fibonacci堆的实现。我不知道为什么会这样，但是我相信是因为斐波那契堆积是以渐近的意义渐近的，他们在实践中有很大的不变因素。集合框架也没有二进制堆，这将是另一个很好的堆栈。

作为一个完全无耻的自我插件，我有一个在我的个人网站上实现Java中的斐波那契堆栈。我不知道它有多有用，但如果你好奇看看它是如何工作的，我认为这可能是一个很好的起点。

希望这有助于！

I was looking at the different kind of heap data structures.

The Fibonacci heap seems to have the better worst case complexity for (1) insertion, (2) deletion and (2) finding the minimum element.

I have found that in Java there is a class PriorityQueue that is a balanced binary heap. But why they did not use a Fibonacci heap?

Also, is there an implementation of a Fibonacci heap in java.util?

Thanks!

解决方案

No, the standard Java collections API does not contain an implementation of a Fibonacci heap. I'm not sure why this is, but I believe it is because while Fibonacci heaps are asymptotically great in an amortized sense, they have huge constant factors in practice. The collections framework also doesn't have a binomial heap, which would be another good heap to include.

As a totally shameless self-plug, I have an implementation of a Fibonacci heap in Java on my personal website. I'm not sure how useful it will be, but if you're curious to see how it works I think it might be a good starting point.

Hope this helps!

这篇关于是否有一个标准的Java实现的斐波纳契堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！