Binomial Heap

Binomial Heap

A binomial heap is implemented as a collection of binomial trees (compare with a binary heap, which has a shape of a single binary tree). A binomial tree is defined recursively:

• A binomial tree of order 0 is a single node
• A binomial tree of order k has a root node whose children are roots of binomial trees of orders k−1, k−2, ..., 2, 1, 0 (in this order).

Binomial trees of order 0 to 3: Each tree has a root node with subtrees of all lower ordered binomial trees, which have been highlighted. For example, the order 3 binomial tree is connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.

A binomial tree of order k has 2^k nodes, height k.

Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k−1 trivially by attaching one of them as the leftmost child of root of the other one. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.

The name comes from the shape: a binomial tree of order  has  nodes at depth . (See Binomial coefficient.)

Structure of a binomial heap

A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties:

• Each binomial tree in a heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent.

• There can only be either one or zero binomial trees for each order, including zero order.

The first property ensures that the root of each binomial tree contains the smallest key in the tree, which applies to the entire heap.

The second property implies that a binomial heap with n nodes consists of at most log n + 1 binomial trees. In fact, the number and orders of these trees are uniquely determined by the number of nodes n: each binomial tree corresponds to one digit in the binary representation of number n. For example number 13 is 1101 in binary, , and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0

http://www.growingwiththeweb.com/2014/01/binomial-heap.html

Operation	Description	Complexity
Decrease key	Decreases an existing key to some value	$\Theta(\log n)$
Delete	Deletes a node given a reference to the node	$\Theta(\log n)$
Extract minimum	Removes and returns the minimum value given a reference to the node	$\Theta(\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	$\Theta(\log n)$**

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

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

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

Please read full article from Binomial Heap