This project provides a Java implementation of Fibonacci Heap. Fibonacci Heap is a heap data structure consisting a collection of min-heap-ordered trees. It is an advanced amortized data structure, whose amortized performance is better than common collections like Linked List. However, some of its operations can run as slowly as linear time in worst case, therefore make it inappropriate for general use. On the other hand, especially in terms of algorithm learning and time analysis, it is a very good data structure.
Introduction to Algorithms (3rd ed) Chap 21 and Wiki give a very detailed discussion of Fibonacci heap. For the sake of simplicity, I only re-print the running time comparison between Linked List and Fibonacci Heap
Operations | Linked List | Fibonacci Heap ------------------------------------------- insert | O(1) | O(1) minimum | O(n) | O(1) extractMin | O(n) | O(log n) union | O(1) | O(1) ------------------------------------------- decreaseKey | O(1) | O(l)* delete | O(1) | O(log n)* * Amortized time
Here are explanations of operations, modified from Introduction to Algorithms (3rd ed)
- insert(x) inserts a node x into the heap.
- minimum() returns the node in the heap with minimum key.
- extractMin() deletes the node with minimum key from the heap.
- union(H) merge heap H and create a new one.
- decreaseKey(x,k) assigns to node x within the heap the new key value k, which is assumed to be no greater than its current key value.
- delete(x) deletes node x from the heap.
FabonacciHeap, much of the code is based on the algorithms in the Introduction to Algorithms (3rd ed) Chap 21. The amortized cost of most of these methods is O(1), making it a very fast data structure. Several have an actual running time of O(1). extractMin() and delete() have O(log n) amortized running times because they do the heap consolidation().
The data structure of a Fibonacci heap is (copied from Warren Armstrong’s website)
For each node
- Two pointers left and right are used to form a circular double linked list.
- One pointer parent is used to its parent.
- One pointer child is used to one of its children.
- degree stores the number of children.
- mark “indicates whether node has lost a child since the last it was make the child of another node.” The boolean mark is very useful to amortize the running time of decrease-key.
- An integer key is used to indicate the key value of the node. Because in delete(), the key needs to set to MIN_VALUE,
Comparablecannot be used for a more general case.
FabonacciHeap provides an implementation of a Fibonacci heap in Java. Although the source code supports many operations on the heap, from the above comparison table, it can be seen that only insert(), minimum(), extractMin(), and union() are recommended to use.
After that, the use of
FibonacciHeap is straightforward.
// construct a heap FibonacciHeap heap = new FibonacciHeap(); FibonacciHeap.Entry n1 = new FibonacciHeap.Entry(23, 0); heap.insert(n1); FibonacciHeap.Entry n2 = new FibonacciHeap.Entry(7, 0); heap.insert(n2); FibonacciHeap.Entry n3 = new FibonacciHeap.Entry(35, 0); heap.insert(n3); // minimum System.out.println(heap.minimum()); // extractMin heap.extractMin(); System.out.println(heap.minimum()); // decrease key heap.decreaseKey(n1, 1); System.out.println(heap.minimum());
To check the inner structure of the heap, I also provide a class
FibonacciHeapString to print the collection of trees.
System.out.println(FibonacciHeapString.toString( heap, new StringBuilder()));