Is there a standard Java implementation of a Fibonacci heap?

java data-structures heap fibonacci-heap
Phil picture Phil · Jun 8, 2011 · Viewed 23.8k times · Source

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!

Answer

templatetypedef picture templatetypedef · Jun 8, 2011

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!

Related questions

How to implement a tree data-structure in Java?

Is there any standard Java library class to represent a tree in Java? Specifically I need to represent the following: The sub-tree at any node can have an arbitrary number of children Each node (after the root) and it's children …

Read More
Get keys from HashMap in Java

I have a Hashmap in Java like this: private Map<String, Integer> team1 = new HashMap<String, Integer>(); Then I fill it like this: team1.put("United", 5); How can I get the keys? Something like: team1.getKey() …

Read More
Java: How to convert List to Map

Recently I have conversation with a colleague about what would be the optimal way to convert List to Map in Java and if there any specific benefits of doing so. I want to know optimal conversion approach and would really …

Read More