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

问题描述

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

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

斐波那契堆似乎在 (1) 插入、(2) 删除和 (2) 找到最小元素方面具有更好的最坏情况复杂度.

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

我发现在 Java 中有一个 PriorityQueue 类，它是一个平衡的二进制堆.但为什么他们不使用斐波那契堆?

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?

另外，java.util 中是否有斐波那契堆的实现?

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

谢谢！

推荐答案

不，标准 Java 集合 API 不包含斐波那契堆的实现.我不确定为什么会这样，但我相信这是因为虽然斐波那契堆在摊销的意义上渐近地很棒，但它们在实践中具有巨大的常数因子.集合框架也没有二项式堆，这将是另一个很好的堆.

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.

作为一个完全无耻的自我插件，我在我的个人网站上有一个用 Java 编写的斐波那契堆的实现.我不确定它会有多大用处，但如果您想知道它是如何工作的，我认为这可能是一个很好的起点.

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.

希望这有帮助！

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