Implementation of a Fibonacci Heap in Java

Today, we show the implementation of a Fibonacci heap. We will show that even theoretically they perform better than a binary heap, e.g.  fibonacci heap inserts in O(1) vs O(log n)  of a binary heap.  In a practical application, its constant factors make them less desirable than a binary heap for most of the applications.

The implementation follows [1, Chapter 19] or [2, Chapter 20].

Implementation:

import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;


public final class FibonacciHeap<E>  extends AbstractQueue<E> {

public static final class Node<E> {
int degree = 0;
boolean mark = false;
private Node<E> parent = null;
private Node<E> child = null;

private Node<E> left = null;
private Node<E> right = null;
private E element;

public E getElement(){return element;}
public void setElement(E element){this.element=element;}

public Node (E elem)
{
this.element=elem;
left = right = this;
}
}

private class DefaultComparator implements Comparator<E>
    {
        public int compare (Object o1, Object o2)
        {
        if(o1==null && o2 ==null)
        return 0;
        if(o1==null)
        return -1;
        if(o2==null)
        return 1;
            return ((Comparable) o1).compareTo(o2);
        }
    }

    private Comparator<E> myComp = new DefaultComparator();
private int size=0;
private Node<E> min=null;

public boolean offer(E e) {
if (e==null)
return false;
Node<E> x = new Node<E>(e);
if (min == null)
{
min = x;
}
else
{
min = mergeLists(min, x);
}
size++;
return true;
}

public boolean isEmpty() {
        return min == null;
    }

public void union(FibonacciHeap<E> h2)
{
min=mergeLists(this.min, h2.min);
this.size += h2.size;
//destroy the added one
h2.min=null;
h2.size=0;
}

public E poll() {
Node<E> z = min;
if (z!=null)
{
if(z.child!=null)
{
Node<E> current =z.child;
do
{
current.parent = null;
current = current.right;
}
while(current != z.child);
}
mergeLists(min, z.child);
if(z.right!=z)
{
z.right.left = z.left;
z.left.right = z.right;
min = z.right;
consolidate();
}
else
min = null;

}
size--;
return z.getElement();
}

private void consolidate() 
{
Object[] A = new Object[(int)(Math.log(size)/Math.log(2))+2];
Node<E> current = min;
HashSet<Node<E>> used = new HashSet<Node<E>>();
do
{
Node<E> x = current;
used.add(x);
current = current.right;
int d = x.degree;
while(A[d] != null)
{
Node<E> y = (Node<E>) A[d];
if (myComp.compare(x.element, y.element)>0)
{
Node<E> temp =x;
x=y;
y=temp;
}
fibHeapLink(y,x);
A[d] = null;
d = d+1;
}
A[d] = x;
}
while(!used.contains(current));


min=null;
for (int i=0; i<A.length; i++)
{
if(A[i] != null)
{
if(min==null)
min=(Node<E>) A[i];
else
min = (Node<E>) (myComp.compare(min.element, ((Node<E>) A[i]).element)<0 ? min : A[i]);
}
}

}

private void fibHeapLink(Node<E>y, Node<E>x)
{
//It cannot be than y is the only one in root list as x has to be too

y.right.left = y.left;
y.left.right = y.right;
y.right=y;
y.left=y;
if(x.child!=null)
{
x.child = mergeLists(x.child, y);
}
else
x.child = y;
x.degree += 1;
y.mark = false;
}

public E peek() {
if(size==0)
return null;
return min.getElement();
}

public int size() {
return size;
}
    
    
private Node<E> mergeLists(Node<E> list1, Node<E> list2) 
{
          if (list1 == null && list2 == null) {
              return null;
          }
          if ( list2 == null) {
              return list1;
          }
          if (list1 == null ) {
              return list2;
          }
          else { 
            // Both non-null; actually do the splice.
            /* The idea is that we'll have two lists that look like this:
             *
             * +----+     +----+     +----+
             * |    |--R->| l1 |--R->|l1R |
             * |    |<-L--|    |<-L--|    |
             * +----+     +----+     +----+
             *
             *
             * +----+     +----+     +----+
             * |    |--R->| l2 |--R->|    |
             * |    |<-L--|    |<-L--|    |
             * +----+     +----+     +----+
             *
             * And we want to relink everything to get
             *
             * +----+     +----+     +----+---+
             * |    |--R->| l1 |     |l1R |   |
             * |    |<-L--|    |     |    |<+ |
             * +----+     +----+<-\  +----+ | |
             *                  \  R        | |
             *                   L  \       R |
             * +----+     +----+  \->+----+ | |
             * |    |--R->| l2 |     |    | | |
             * |    |<-L--|    |     |    | | L
             * +----+     +----+     +----+ | |
             *              ^ |             | |
             *              | +-------------+ |
             *              +-----------------+
             *
             */
            Node<E> l1R = list1.right;
            list1.right = list2.right;
            list1.right.left =list1;
            list2.right = l1R;
            list2.right.left = list2;

            /* Return a pointer to whichever is smaller. */
            return myComp.compare(list1.element, list2.element)<0 ? list1 : list2;
        }
    }

private void print(Node<E> node, String prefix, boolean start)
{
if(node == null)
return;
System.out.println(prefix + node.getElement().toString());
print(node.child, prefix+"\t", true);
if(start)
{
Node<E> current=node.right;
while(current!=node)
{
print(current, prefix, false);
current = current.right;
}
}
}

public void print()
{
print(min);
}

private void print(Node<E> e)
{
print(e, "", true);
}

public void decreaseKey(Node<E> x, E val)
{
if(myComp.compare(val,x.getElement())>0)
throw new IllegalArgumentException("New key is greater than current");
x.setElement(val);
Node<E> y = x.parent;
if (y != null && myComp.compare(x.getElement(), y.getElement())<0)
{
cut(x,y);
cascadingCut(y);
}
if(myComp.compare(x.getElement(), min.getElement())<0)
min=x;
}

private void cut(Node<E> x, Node<E> y)
{
if(x.right==x)
y.child = null;
else
{
x.left.right = x.right;
x.right.left = x.left;
if (y.child == x)
y.child = x.right;
x.right = x.left = x;
}
min = mergeLists(x, min);
x.parent = null;
x.mark = false;
}

private void cascadingCut(Node<E> y) 
{
Node<E> z = y.parent;
if (z != null)
{
if(y.mark == false)
y.mark=true;
else
{
cut(y,z);
cascadingCut(z); 
}
}
}



public Iterator<E> iterator() {
Iterator<E> it = new Iterator<E>() {
public boolean hasNext() {
return visited.size()<size;
}

public E next() {
E value = current.getElement();
visited.add(current);
if(hasNext())
{
if(current.child!=null)
{
stack.push(current);
current = current.child;
}
else
{
while(visited.contains(current.right))
{
if(!stack.isEmpty())
current = stack.pop();
else
throw new ConcurrentModificationException();
}
current = current.right;
}
}
return value;
}

public void remove() {
throw new UnsupportedOperationException("remove not implemented");
}
Node<E> current = min;
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
HashSet<Node<E>> visited = new HashSet<Node<E>>(); 
};
        
return it;
}
 
public void delete(Node<E> node)
{
decreaseKey(node, null); // We use null to indicate -Inf
poll();
}
}


We also make two experiments to check the know problem of the constant factor. The first one consists on generating 1,000,000 random numbers and add them to a heap and after extract all of them, the second we just extract one of them. We compare the Fibonacci heap here implemented with a binary heap (PriorityQueue class)

Results:

                                Binary Heap           Fibonacci Heap
Experiment 1            685.396 ms             4707.570 ms
Experiment 2             82.292 ms              1231.942 ms




[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduction to Algorithms", McGraw-Hill, 3rd Edition.

[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduction to Algorithms", McGraw-Hill, 2nd Edition.