Basic introduction to fibonacci heaps and some comparson with regular heaps.

Operations Supported

Complexity Comparsions With Binary-Heaps

  Binary Heap Worse-Case Fib-Heap Amortized
insert $\Theta(lgn)$ $\Theta(1)$
extract-min $\Theta(lgn)$ $O(lgn)$
decrease-priority $\Theta(lgn)$ $\Theta(1)$
union $\Theta(n)$ $\Theta(1)$

Structure

A fibonnacci heap includes the following components:

For each node, it contains following fields:

Operations

Insert

Insert is very simple, you simply insert into the root linked-list. This takes $O(1)$.

insert(H, x) {
    node = new Node(x);
    node.marked = false;
    // Insert right after H.min
    node.right = H.min.right;
    node.left = H.min;
    H.min.right = node;
    node.right.left = node;
}

Union

Just merge two root lists and it is done. This also takes $O(1)$.

Of course if you want to make a copy this takes longer.

union(H1, H2) {
    connect H1.min and H2.min
}