# 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.

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.

## 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’.

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.

## 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.

### 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.

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.

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.

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.

### Insert

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

### 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.

## 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>> {

public BinomialHeap() {
}

}

public boolean isEmpty() {
}

public void clear() {
}

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

public T findMinimum() {
return null;
} else {
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>>();
while (!nodes.isEmpty()) {
Node<T> curr = nodes.get(0);
nodes.remove(0);
if (curr.key == key) {
return curr;
}
if (curr.sibling != null) {
}
if (curr.child != null) {
}
}
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);
removeTreeRoot(node, null);
} else {
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() {
return null;
}

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
} else {
prev.sibling = root.sibling;
}

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

}

// 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) {

return null;
}

Node<T> prev = null;

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;
} else {
if (prev == null) {
} else {
prev.sibling = next;
}

curr = next;
}
}

next = curr.sibling;
}

}

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

heap1Next = heap1Next.sibling;
} else {
heap2Next = heap2Next.sibling;
}

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;
}

}
}

public void print() {
System.out.println("Binomial heap:");
}
}

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.nodeCount = 0;

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

/**
* Clears the heap's data, making it an empty heap.
*/
BinomialHeap.prototype.clear = function () {
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 () {
return undefined;
}

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 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.nodeCount++;
this.union(tempHeap);
return newNode;
};

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

/**
* @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;

return undefined;
}

var prev;

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;
} else {
if (typeof prev === 'undefined') {
} else {
prev.sibling = next;
}

curr = next;
}

next = curr.sibling;
}

};

/**
* 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') {
}
if (typeof b.head === 'undefined') {
}

aNext = aNext.sibling;
} else {
bNext = bNext.sibling;
}

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;

}

/**
* 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.
*/
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
} else {
prev.sibling = root.sibling;
}

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

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.