Is there a standard Java implementation of a Fibonacci heap?

Question

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!

java collections provide only the most common data structures. I suppose Fibonacci heap is more specialised, or perhaps it is using more memory. — Denis Tulskiy, Jun 08 '11 at 03:31
@James, what does that matter with the Fibonacci heap anyway? o.o — ignis, Jun 08 '11 at 05:31
https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/FibonacciMinPQ.html — maplemaple, Aug 22 '19 at 19:45

templatetypedef · Accepted Answer · 2013-11-28T06:47:36.230

54

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!

edited Nov 28 '13 at 06:47

answered Jun 08 '11 at 03:24

templatetypedef

362,284
104
897
1,065

Thanks a lot. Your implementation looks well-done and well documented with many explanations. I will have a look at this. – Phil Jun 08 '11 at 03:55
Wow, I was going to write my own for fun but yours is so nice! – Andy Dec 18 '13 at 14:13
How does it perform in reality? The Fibonacci heap seems to have quite a lot of memory overhead. – Has QUIT--Anony-Mousse Oct 09 '15 at 20:35
@Anony-Mousse Fibonacci heaps are notoriously slow in practice for precisely the reason you've mentioned. – templatetypedef Oct 09 '15 at 20:39

score 5 · Answer 2 · edited Feb 07 '19 at 12:58

But why they did not use a Fibonacci heap?

Probably because those heaps have a lot more overhead per entry than binary keys.

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

No, but

There is graphmaker from Nathan Fiedler - GPL and with good test coverage, but have a look into this nice blog post about it and about problems a fibonacci impl can have. In this post a lot of other Java implementions are referenced.
There is some code with unit tests here
The JGraphT project (also Nathan Fiedler) and also with (some minor) tests but LGPL.
Last but not least there is Neo4j - GPL - no tests.

score 1 · Answer 3 · edited Oct 22 '17 at 18:00

1

But why they did not use a Fibonacci heap?

I think the main reason is because the Fibonacci heap can only help in the case when you have lot more decreaseKey operation connected to one extractMin operation. For example, when you are using it with the Dijkstra's algorithm.

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

There is no implementation in Java.util, but I did some experiment on this topic using existing open-source versions of the Fibonacci heap. You can find it on my blog or on the project's GitHub repository.

edited Oct 22 '17 at 18:00

Nat

3,587
20
22

answered Feb 12 '15 at 18:56

gabormakrai

21
1

Can you please elaborate on your answer for the first question – arunmoezhi Feb 12 '15 at 19:23
Of course I can. Fibonacci Heap has superiority over Binary Heap on executing decreaseKey and insert operations, also it has the same time complexity for extractMin, but this operation takes much more time for FH than BH, because it is consolidating the inner tree forest. So if you have a very few decreaseKey then it is slower than the normal Binary Heap. For some special graphs, that's the case for the Dijkstra's algorithm. – gabormakrai Feb 12 '15 at 22:10

Is there a standard Java implementation of a Fibonacci heap?

3 Answers3

Linked