Binomial heap

In computer science, a binomial heap is a data structure that acts as a priority queue.

[1] Binomial heaps were invented in 1978 by Jean Vuillemin.

[1][2] A binomial heap is implemented as a set of binomial trees (compare with a binary heap, which has a shape of a single binary tree), which are defined recursively as follows:[1] A binomial tree of order

The name comes from the shape: a binomial tree of order

by attaching one of them as the leftmost child of the root of the other tree.

This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.

It follows that the smallest key in the entire heap is one of the roots.

: there is one binomial tree for each nonzero bit in the binary representation of the number

items with distinct keys can be arranged into a binomial heap equals the largest odd divisor of

items are inserted into a binomial heap in a uniformly random order, each of these arrangements is equally likely.

[3] Because no operation requires random access to the root nodes of the binomial trees, the roots of the binomial trees can be stored in a linked list, ordered by increasing order of the tree.

Because the number of children for each node is variable, it does not work well for each node to have separate links to each of its children, as would be common in a binary tree; instead, it is possible to implement this tree using links from each node to its highest-order child in the tree, and to its sibling of the next smaller order than it.

These sibling pointers can be interpreted as the next pointers in a linked list of the children of each node, but with the opposite order from the linked list of roots: from largest to smallest order, rather than vice versa.

This representation allows two trees of the same order to be linked together, making a tree of the next larger order, in constant time.

A basic subroutine within this procedure merges pairs of binomial trees of the same order.

The root node with the larger key is made into a child of the root node with the smaller key, increasing its order by one:[1][3] To merge two heaps more generally, the lists of roots of both heaps are traversed simultaneously in a manner similar to that of the merge algorithm, in a sequence from smaller orders of trees to larger orders.

[1][3] Because each binomial tree in a binomial heap corresponds to a bit in the binary representation of its size, there is an analogy between the merging of two heaps and the binary addition of the sizes of the two heaps, from right-to-left.

[1][3] Each binomial tree's traversal during merge only involves roots, hence making the time taken at most order

Because of the merge, a single insertion takes time

Another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive insert has an amortized time of

[1][3] A variant of the binomial heap, the skew binomial heap, achieves constant worst case insertion time by using forests whose tree sizes are based on the skew binary number system rather than on the binary number system.

[1] By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to

The pointer must be updated when performing any operation other than finding the minimum.

[citation needed] To delete the minimum element from the heap, first find this element, remove it from the root of its binomial tree, and obtain a list of its child subtrees (which are each themselves binomial trees, of distinct orders).

Transform this list of subtrees into a separate binomial heap by reordering them from smallest to largest order.

children, creating this new heap takes time

, so the entire delete minimum operation takes time

If this is the case, exchange the element with its parent, and possibly also with its grandparent, and so on, until the minimum-heap property is no longer violated.

[1] However, this operation requires that the representation of the tree include pointers from each node to its parent in the tree, somewhat complicating the implementation of other operations.

[1] Here are time complexities[5] of various heap data structures.

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.
Example of a binomial heap
Example of a binomial heap containing 13 nodes with distinct keys. The heap consists of three binomial trees with orders 0, 2, and 3.
To merge two binomial trees of the same order, first compare the root key. Since 7>3, the black tree on the left (with root node 7) is attached to the grey tree on the right (with root node 3) as a subtree. The result is a tree of order 3.
This shows the merger of two binomial heaps. This is accomplished by merging two binomial trees of the same order one by one. If the resulting merged tree has the same order as one binomial tree in one of the two heaps, then those two are merged again.