Fibonacci Heap Java Implementation

Intro to heaps:
Briefly said heap is a data structure like stack, linked list s.o.

Features:
Usually you should be able to to perform the following operations "quickly":
- get min/max element
- add new element
- join two heaps
- decrease a key of element

Disadvantages:
- heaps cannot perform fast search operations. The only way for most classic implementations of a heap to perform a search is to scan all of the elements which takes linear time.

There are many variants of a heaps. Here you can find more about heaps:
Heaps Wikipedia Article

Fibonacci Heap:
Fibonacci Heap Wikipedia Article
As you can see Fibonacci heap offers faster running times compared to many of the other heaps.

So enough said about the structure. Here is a implementation in Java 1.6 of the Fibonacci heap.It supports the following operations - insert, extract min, decrease key. This is all you need if you want to implement Dijkstra's shortest path algorithm for instance. The operations union and delete min are not added but if you need you can add them easily since they are trivial.
A drawback of this implementation(and probably any implementation of Fibonacci heap) is the high constant compared to array based binary heap for example.



API summary:

Maybe you will find the API offered a bit unclear and strange.I agree with that but here is the reason it looks like this - as we mentioned there is no fast way to find element in a heap.So if we want to decrease key of random element effectively we cannot afford to waste time searching for this element. We should have reference to it and pass it directly to the decreaseKey method.
These references to elements in the heap are obtained via the insert method which gives you reference to the newly added element.

So if you do not intend to use the decrease key operation you can write you own wrapper class and provide much more user friendly api design.

API Javadoc


Tests:

There are some JUnit tests provided which test almost all of the functionality.Code coverage is about 95%.


Performance:

As mentioned fibonacci heap implementations have big constant.
This implementation could be slightly improved by modifying it not to use head and tail references for the main list. Only reference to the min element is sufficient.This might save some time.In the test package you can also find performance test comparing java PriorityQueue(which implements binary heap) with this implementation. You can play with different parameters for tests and check out how both heaps behave.
---------
Note: If you want to test for inserting/extracting a few million elements you might have to set this VM arguments:
vm args -Xms128m -Xmx512m (in Eclipse this is done in the running configurations of the test)
---------
Results vary for different parameters so it really depends on the use case to tell which one is better.
PriorityQueue doesn't support decrease key operation so it cannot be compared but if it supported it should be supposedly slower since its running time is O(log n) while this implementation of decrease key has running time O(1) amortized.
Union operation is also much faster for Fibonacci heaps - O(1) while it takes O(n) for binary heaps.So as I mentioned adding it to this implementation is a piece of cake and if you use it you will get much better performance.

So finally here is the full source with the tests:

Fibonacci Heap source + tests

If you find bugs or ways to make it faster feel free to tell me.