Growing with the Web

Binomial heap

Published , updated
Tags:

A binomial heap is a priority queue data structure similar to the binary heap only with a more strict structure, it supports quicker merging of two heaps in Θ(\log n) at the cost of a slower find minimum operation. A binomial heap is made up of a series of unique ‘binomial trees’ which are constructed from smaller binomial trees.

Binomial heap

Just like a regular binary heap, the binomial heap can be either a min heap or a max heap. It also follows the properties of the heap data structure; all nodes must be smaller than their children for a min heap, or larger for a max heap.

The animations in this article rely on CSS transforms on SVG which is not yet implemented in Edge.

Complexity

Operation Description Complexity
Decrease key Decreases an existing key to some value Θ(\log n)
Delete Deletes a node given a reference to the node Θ(\log n)
Extract minimum Removes and returns the minimum value given a reference to the node Θ(\log n)
Find minimum Returns the minimum value O(\log n)*
Insert Inserts a new value O(\log n)
Union Combine the heap with another to form a valid binomial heap Θ(\log n)**

* This can be reduced to Θ(1) by maintaining a pointer to the minimum element
** Where n is the size of the larger heap

Structure

A binomial heap is made of a series of binomial trees each of which have a unique order. The order of a binomial tree defines how many elements it can contain, namely 2^{order}. Each tree of the order x is constructed by linking trees of the order x - 1, x - 2, … 1, 0 together.

An interesting property of the structure is that it resembles the binary number system. For example, a binomial heap with 30 elements will have binomial trees of the order 1, 2, 3 and 4, which are in the same positions as the number 30 in binary ‘11110’.

Structure

The typical method of implementing the links between nodes is to have pointers to a parent, sibling and child. A tree does not have a direct link to all it’s immediate children, instead it goes to its first child and then iterates through each sibling. Here is an illustration of the regular pointer structure for a binomial tree.

Links

Operations

Decrease key

Decrease key reduces the specified node’s key and then bubbles it up through its ancestors until the tree meets the conditions of a heap.

Binomial heap decrease key operation example, your browser doesn't support SVG.

Delete

Delete is performed by calling decrease key to reducing the node to negative infinity which pulls the node to the top of the tree.

Binomial heap delete step 1 operation example, your browser doesn't support SVG.

The tree is then detached from the rest of the heap and the node removed. The fragments of the old tree are reversed and linked together to form a new heap.

Binomial heap delete step 2 operation example, your browser doesn't support SVG.

The two heaps can then be combined using the union operation.

Extract minimum

Extract minimum iterates through the roots of each binomial tree in the heap to find the smallest node which is removed. The tree fragments are then reversed to form another heap.

Binomial heap extract minimum operation example, your browser doesn't support SVG.

The two heaps can then be combined using the union operation.

Find minimum

Find minimum iterates through the roots of each binomial tree in the heap.

Find minimum

Insert

Insert creates a new heap with the inserted element which are then combined using the union operation.

Insert

Union

The union operation merges the two heaps together by continually linking trees of the same order until no two trees of the same order exist.

Binomial heap union operation example, your browser doesn't support SVG.

Code

The below is a generic implementation of a min binomial heap that uses the value stored as the key.

public class BinomialHeap<T extends Comparable<T>> {

    private Node<T> head;

    public BinomialHeap() {
        head = null;
    }

    public BinomialHeap(Node<T> head) {
        this.head = head;
    }

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

    public void clear() {
        head = null;
    }

    public void insert(T key) {
        Node<T> node = new Node<T>(key);
        BinomialHeap<T> tempHeap = new BinomialHeap<T>(node);
        head = union(tempHeap);
    }

    public T findMinimum() {
        if (head == null) {
            return null;
        } else {
            Node<T> min = head;
            Node<T> next = min.sibling;

            while (next != null) {
                if (next.compareTo(min) < 0) {
                    min = next;
                }
                next = next.sibling;
            }

            return min.key;
        }
    }

    // Implemented to test delete/decrease key, runs in O(n) time
    public Node<T> search(T key) {
        List<Node<T>> nodes = new ArrayList<Node<T>>();
        nodes.add(head);
        while (!nodes.isEmpty()) {
            Node<T> curr = nodes.get(0);
            nodes.remove(0);
            if (curr.key == key) {
                return curr;
            }
            if (curr.sibling != null) {
                nodes.add(curr.sibling);
            }
            if (curr.child != null) {
                nodes.add(curr.child);
            }
        }
        return null;
    }

    public void decreaseKey(Node<T> node, T newKey) {
        node.key = newKey;
        bubbleUp(node, false);
    }

    public void delete(Node<T> node) {
        node = bubbleUp(node, true);
        if (head == node) {
            removeTreeRoot(node, null);
        } else {
            Node<T> prev = head;
            while (prev.sibling.compareTo(node) != 0) {
                prev = prev.sibling;
            }
            removeTreeRoot(node, prev);
        }
    }

    private Node<T> bubbleUp(Node<T> node, boolean toRoot) {
        Node<T> parent = node.parent;
        while (parent != null && (toRoot || node.compareTo(parent) < 0)) {
            T temp = node.key;
            node.key = parent.key;
            parent.key = temp;
            node = parent;
            parent = parent.parent;
        }
        return node;
    }

    public T extractMin() {
        if (head == null) {
            return null;
        }

        Node<T> min = head;
        Node<T> minPrev = null;
        Node<T> next = min.sibling;
        Node<T> nextPrev = min;

        while (next != null) {
            if (next.compareTo(min) < 0) {
                min = next;
                minPrev = nextPrev;
            }
            nextPrev = next;
            next = next.sibling;
        }

        removeTreeRoot(min, minPrev);
        return min.key;
    }

    private void removeTreeRoot(Node<T> root, Node<T> prev) {
        // Remove root from the heap
        if (root == head) {
            head = root.sibling;
        } else {
            prev.sibling = root.sibling;
        }

        // Reverse the order of root's children and make a new heap
        Node<T> newHead = null;
        Node<T> child = root.child;
        while (child != null) {
            Node<T> next = child.sibling;
            child.sibling = newHead;
            child.parent = null;
            newHead = child;
            child = next;
        }
        BinomialHeap<T> newHeap = new BinomialHeap<T>(newHead);

        // Union the heaps and set its head as this.head
        head = union(newHeap);
    }

    // Merge two binomial trees of the same order
    private void linkTree(Node<T> minNodeTree, Node<T> other) {
        other.parent = minNodeTree;
        other.sibling = minNodeTree.child;
        minNodeTree.child = other;
        minNodeTree.degree++;
    }

    // Union two binomial heaps into one and return the head
    public Node<T> union(BinomialHeap<T> heap) {
        Node<T> newHead = merge(this, heap);

        head = null;
        heap.head = null;

        if (newHead == null) {
            return null;
        }

        Node<T> prev = null;
        Node<T> curr = newHead;
        Node<T> next = newHead.sibling;

        while (next != null) {
            if (curr.degree != next.degree || (next.sibling != null &&
                    next.sibling.degree == curr.degree)) {
                prev = curr;
                curr = next;
            } else {
                if (curr.compareTo(next) < 0) {
                    curr.sibling = next.sibling;
                    linkTree(curr, next);
                } else {
                    if (prev == null) {
                        newHead = next;
                    } else {
                        prev.sibling = next;
                    }

                    linkTree(next, curr);
                    curr = next;
                }
            }

            next = curr.sibling;
        }

        return newHead;
    }

    private static <T extends Comparable<T>> Node<T> merge(
            BinomialHeap<T> heap1, BinomialHeap<T> heap2) {
        if (heap1.head == null) {
            return heap2.head;
        } else if (heap2.head == null) {
            return heap1.head;
        } else {
            Node<T> head;
            Node<T> heap1Next = heap1.head;
            Node<T> heap2Next = heap2.head;

            if (heap1.head.degree <= heap2.head.degree) {
                head = heap1.head;
                heap1Next = heap1Next.sibling;
            } else {
                head = heap2.head;
                heap2Next = heap2Next.sibling;
            }

            Node<T> tail = head;

            while (heap1Next != null && heap2Next != null) {
                if (heap1Next.degree <= heap2Next.degree) {
                    tail.sibling = heap1Next;
                    heap1Next = heap1Next.sibling;
                } else {
                    tail.sibling = heap2Next;
                    heap2Next = heap2Next.sibling;
                }

                tail = tail.sibling;
            }

            if (heap1Next != null) {
                tail.sibling = heap1Next;
            } else {
                tail.sibling = heap2Next;
            }

            return head;
        }
    }

    public void print() {
        System.out.println("Binomial heap:");
        if (head != null) {
            head.print(0);
        }
    }

    public static class Node<T extends Comparable<T>>
            implements Comparable<Node<T>> {
        public T key;
        public int degree;
        public Node<T> parent;
        public Node<T> child;
        public Node<T> sibling;

        public Node() {
            key = null;
        }

        public Node(T key) {
            this.key = key;
        }

        public int compareTo(Node<T> other) {
            return this.key.compareTo(other.key);
        }

        public void print(int level) {
            Node<T> curr = this;
            while (curr != null) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < level; i++) {
                    sb.append(" ");
                }
                sb.append(curr.key.toString());
                System.out.println(sb.toString());
                if (curr.child != null) {
                    curr.child.print(level + 1);
                }
                curr = curr.sibling;
            }
        }
    }

}
'use strict';

/**
 * Creates a binomial heap.
 *
 * @constructor
 * @param {function} customCompare An optional custom node comparison
 * function.
 */
var BinomialHeap = function (customCompare) {
  this.head = undefined;
  this.nodeCount = 0;

  if (customCompare) {
    this.compare = customCompare;
  }
};

/**
 * Clears the heap's data, making it an empty heap.
 */
BinomialHeap.prototype.clear = function () {
  this.head = undefined;
  this.nodeCount = 0;
};

/**
 * Extracts and returns the minimum node from the heap.
 *
 * @return {Node} node The heap's minimum node or undefined if the heap is
 * empty.
 */
BinomialHeap.prototype.extractMinimum = function () {
  if (!this.head) {
    return undefined;
  }

  var min = this.head;
  var minPrev;
  var next = min.sibling;
  var nextPrev = min;

  while (next) {
    if (this.compare(next, min) < 0) {
      min = next;
      minPrev = nextPrev;
    }
    nextPrev = next;
    next = next.sibling;
  }

  removeTreeRoot(this, min, minPrev);
  this.nodeCount--;

  return min;
};

/**
 * Returns the minimum node from the heap.
 *
 * @return {Node} node The heap's minimum node or undefined if the heap is
 * empty.
 */
BinomialHeap.prototype.findMinimum = function () {
  if (typeof this.head === 'undefined') {
    return undefined;
  }

  var min = this.head;
  var next = min.sibling;

  while (next) {
    if (this.compare(next, min) < 0) {
      min = next;
    }
    next = next.sibling;
  }

  return min;
};

/**
 * Inserts a new key-value pair into the heap.
 *
 * @param {Object} key The key to insert.
 * @param {Object} value The value to insert.
 * @return {Node} node The inserted node.
 */
BinomialHeap.prototype.insert = function (key, value) {
  var tempHeap = new BinomialHeap();
  var newNode = new Node(key, value);
  tempHeap.head = newNode;
  tempHeap.nodeCount++;
  this.union(tempHeap);
  return newNode;
};

/**
 * @return {boolean} Whether the heap is empty.
 */
BinomialHeap.prototype.isEmpty = function () {
  return !this.head;
};

/**
 * @return {number} The size of the heap.
 */
BinomialHeap.prototype.size = function () {
  return this.nodeCount;
};

/**
 * Joins another heap to this one.
 *
 * @param {BinomialHeap} otherHeap The other heap.
 */
BinomialHeap.prototype.union = function (heap) {
  this.nodeCount += heap.nodeCount;

  var newHead = mergeHeaps(this, heap);

  this.head = undefined;
  heap.head = undefined;

  if (!newHead) {
    return undefined;
  }

  var prev;
  var curr = newHead;
  var next = newHead.sibling;

  while (next) {
    if (curr.degree !== next.degree ||
        (next.sibling && next.sibling.degree === curr.degree)) {
      prev = curr;
      curr = next;
    } else if (this.compare(curr, next) < 0) {
      curr.sibling = next.sibling;
      linkTrees(curr, next);
    } else {
      if (typeof prev === 'undefined') {
        newHead = next;
      } else {
        prev.sibling = next;
      }

      linkTrees(next, curr);
      curr = next;
    }

    next = curr.sibling;
  }

  this.head = newHead;
};

/**
 * Compares two nodes with each other.
 *
 * @private
 * @param {Object} a The first key to compare.
 * @param {Object} b The second key to compare.
 * @return {number} -1, 0 or 1 if a < b, a == b or a > b respectively.
 */
BinomialHeap.prototype.compare = function (a, b) {
  if (a.key > b.key) {
    return 1;
  }
  if (a.key < b.key) {
    return -1;
  }
  return 0;
};

/**
 * Merges two heaps together.
 *
 * @private
 * @param {Node} a The head of the first heap to merge.
 * @param {Node} b The head of the second heap to merge.
 * @return {Node} The head of the merged heap.
 */
function mergeHeaps(a, b) {
  if (typeof a.head === 'undefined') {
    return b.head;
  }
  if (typeof b.head === 'undefined') {
    return a.head;
  }

  var head;
  var aNext = a.head;
  var bNext = b.head;

  if (a.head.degree <= b.head.degree) {
    head = a.head;
    aNext = aNext.sibling;
  } else {
    head = b.head;
    bNext = bNext.sibling;
  }

  var tail = head;

  while (aNext && bNext) {
    if (aNext.degree <= bNext.degree) {
      tail.sibling = aNext;
      aNext = aNext.sibling;
    } else {
      tail.sibling = bNext;
      bNext = bNext.sibling;
    }

    tail = tail.sibling;
  }

  tail.sibling = aNext ? aNext : bNext;

  return head;
}

/**
 * Link two binomial trees of the same order.
 *
 * @private
 * @param {Node} minNodeTree The head of the first tree to link.
 * @param {Node} other The head of the second tree to link.
 */
function linkTrees(minNodeTree, other) {
  other.parent = minNodeTree;
  other.sibling = minNodeTree.child;
  minNodeTree.child = other;
  minNodeTree.degree++;
}

/**
 * Link two binomial trees of the same order.
 *
 * @private
 * @param {Node} minNodeTree The head of the first tree to link.
 * @param {Node} other The head of the second tree to link.
 */
function removeTreeRoot(heap, root, prev) {
  // Remove root from the heap
  if (root === heap.head) {
    heap.head = root.sibling;
  } else {
    prev.sibling = root.sibling;
  }

  // Reverse the order of root's children and make a new heap
  var newHead;
  var child = root.child;
  while (child) {
    var next = child.sibling;
    child.sibling = newHead;
    child.parent = undefined;
    newHead = child;
    child = next;
  }
  var newHeap = new BinomialHeap();
  newHeap.head = newHead;

  heap.union(newHeap);
}

/**
 * Creates a Binomial Heap node.
 *
 * @constructor
 * @param {Object} key The key of the new node.
 * @param {Object} value The value of the new node.
 */
function Node(key, value) {
  this.key = key;
  this.value = value;
  this.degree = 0;
  this.parent = undefined;
  this.child = undefined;
  this.sibling = undefined;
}

module.exports = BinomialHeap;

References

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Binomial Heaps” in Introduction to Algorithms, 2nd ed., Cambridge, MA: The MIT Press, 2001, ch. 19, pp.455-475

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!