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

Operations Supported

  • make_heap - Create a new heap.
  • insert(H, x) - Insert x into heap H.
  • min(H) - Return minimum element in H.
  • extract_min(H) - Return minimum element in H and removes it.
  • union(H1, H2) - Creates and returns a new heap containing all elements in H1 and H2.
  • decrease_key(H, x, k) - Assigns x in H a new key k. k must be less then the current key.
  • delete(H, x) - Delete element x from heap H.

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:

  • A forest of heap-ordered trees.
  • Roots of these trees are stored in a circular doubly-linked list.
  • Pointer to minimum root, and total number of nodes.
  • Siblings in a circular doubly-linked list, parent only knows one child.
  • deg(x) is number of children is x’s child list.

For each node, it contains following fields:

  • key: Priority
  • left, right, parent: Pointers
  • child: Pointer to one child
  • degree: Num of children
  • mark: Boolean, useful for decrease-priority

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
}