Binomial heap
In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged together.
It is important as an implementation of the mergeable heap abstract data type, which is a priority queue supporting merge operation. 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.
Binomial heap
A binomial heap is implemented as a set of binomial trees, which are defined recursively as follows:- A binomial tree of order 0 is a single node
- A binomial tree of order has a root node whose children are roots of binomial trees of orders,,..., 2, 1, 0.
The name comes from the shape: a binomial tree of order has nodes at depth, a binomial coefficient.
Because of its structure, a binomial tree of order can be constructed from two trees 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.
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 second property implies that a binomial heap with nodes consists of at most binomial trees, where is the binary logarithm. The number and orders of these trees are uniquely determined by the number of nodes : there is one binomial tree for each nonzero bit in the binary representation of the number. For example, the decimal 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.
Example of a binomial heap containing 13 nodes with distinct keys.
The heap consists of three binomial trees with orders 0, 2, and 3.
The number of different ways that items with distinct keys can be arranged into a binomial heap equals the largest odd divisor of. For these numbers are
If the items are inserted into a binomial heap in a uniformly random order, each of these arrangements is equally likely.
Implementation
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.Merge
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 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
if p.root.key <= q.root.key
return p.addSubTree
else
return q.addSubTree
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, this tree is moved to the output heap. When both of the two heaps contain a tree of order, the two trees are merged to one tree of order so that the minimum-heap property is satisfied. It may later become necessary to merge this tree with some other tree of order in one of the two input heaps. In the course of the algorithm, it will examine at most three trees of any order, two from the two heaps we merge and one composed of two smaller trees.
function merge
while not and q.end)
tree = mergeTree, q.currentTree)
if not heap.currentTree.empty
tree = mergeTree)
heap.addTree
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 tree has order at most and therefore the running time is.
Insert
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. However, this can be sped up using a merge procedure that shortcuts the merge after it reaches a point where only one of the merged heaps has trees of larger order. With this speedup, across a series of consecutive insertions, the total time for the insertions is. Another way of stating this is that each successive insert has an amortized time of per insertion.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.
Find minimum
To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can be done in time, as there are just tree roots to examine.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. This can be done in time per update, without raising the overall asymptotic running time of any operation.
Delete minimum
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. 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 children, creating this new heap takes time. Merging heaps takes time, so the entire delete minimum operation takes time.function deleteMin
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
heap.removeTree
merge