## A Java Implementation of Fibonacci Heap

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)

inserts a node*insert(x)**x*into the heap.returns the node in the heap with minimum key.*minimum()*deletes the node with minimum key from the heap.*extractMin()*merge heap*union(H)**H*and create a new one.assigns to node*decreaseKey(x,k)**x*within the heap the new key value*k*, which is assumed to be no greater than its current key value.deletes node*delete(x)**x*from the heap.

## Implementation

In `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 `FibonacciHeap.Entry`

,

- 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*,`Comparable`

cannot be used for a more general case.

## Usage

`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());