# A Java Implementation of Fibonacci Heap

By | September 21, 2013

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.

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

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

## One thought on “A Java Implementation of Fibonacci Heap”

1. Robin

Where can i find the Implementation of FinbonacciHeap you wrote?

This site uses Akismet to reduce spam. Learn how your comment data is processed.