| Binomial heap | |
| Type: | heap |
| Invented By: | Jean Vuillemin |
| Invented Year: | 1978 |
| Insert Avg: | Θ(1) |
| Insert Worst: | O(log n) |
| Delete Min Avg: | Θ(log n) |
| Delete Min Worst: | O(log n) |
| Find Min Avg: | Θ(1) |
| Find Min Worst: | O(1) |
| Decrease Key Avg: | Θ(log n) |
| Decrease Key Worst: | O(log n) |
| Merge Avg: | Θ(log n) |
| Merge Worst: | O(log n) |
In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.[1]
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:
k
k-1
k-2
A binomial tree of order
k
2k
k
k
\tbinomkd
d
k
k-1
A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties:
The first property ensures that the root of each binomial tree contains the smallest key in the tree. It follows that the smallest key in the entire heap is one of the roots.
The second property implies that a binomial heap with
n
1+log2n
log2
n
n
23+22+20
The number of different ways that
n
n!
n=1,2,3,...
1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... If the
n
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.
The operation of merging two heaps is used as a subroutine in most other operations.A basic subroutine within this procedure merges pairs of binomial trees of the same order. This may be done by comparing the keys at the roots of the two trees (the smallest keys in both trees). 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:
function mergeTree(p, q) if p.root.key <= q.root.key return p.addSubTree(q) else return q.addSubTree(p)
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. When only one of the two heaps being merged contains a tree of order
j
j
j+1
j+1
function merge(p, q) while not (p.end and q.end) tree = mergeTree(p.currentTree, q.currentTree)
if not heap.currentTree.empty tree = mergeTree(tree, heap.currentTree)
heap.addTree(tree) heap.next; p.next; q.next
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. Whenever a carry occurs during addition, this corresponds to a merging of two binomial trees during the merge.
Each binomial tree's traversal during merge only involves roots, hence making the time taken at most order
log2n
O(logn)
Inserting a new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Because of the merge, a single insertion takes time
O(logn)
k
O(k+logn)
O(1)
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.
To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can be done in
O(logn)
O(logn)
By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to
O(1)
O(logn)
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. Then merge this heap with the original heap. Since each root has at most
log2n
O(logn)
O(logn)
O(logn)
function deleteMin(heap) min = heap.trees.first for each current in heap.trees if current.root < min.root then min = current for each tree in min.subTrees tmp.addTree(tree) heap.removeTree(min) merge(heap, tmp)
After decreasing the key of an element, it may become smaller than the key of its parent, violating the minimum-heap property. 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. Each binomial tree has height at most
log2n
O(logn)
To delete an element from the heap, decrease its key to negative infinity (or equivalently, to some value lower than any element in the heap) and then delete the minimum in the heap.