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 2k 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 the other one. 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 : 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 elements consists of at most n + 1 binomial trees. In fact, the number and orders of these trees are uniquely determined by the number of elements n: each binomial tree corresponds to digit one in the representation of number n. For example number 13 is 1101 in binary, 23 + 22 + 20, and thus a binomial heap with 13 elements will consist of three binomial trees of orders 3, 2, and 0 (see figure below).
Example of a binomial heap containing 13 elements with distinct keys.
The heap consists of three binomial trees with orders 0, 2, and 3.
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 , ordered by increasing order of the tree.
Merge
As mentioned above, the simplest and most important operation is the
merging of two binomial trees of the same order within two binomial
heaps. Due to the structure of binomial trees, they can be merged
trivially. As their root node is the smallest element within the tree,
by comparing the two keys, the smaller of them is the minimum key, and
becomes the new root node. Then the other tree become a subtree of the
combined tree. This operation is basic to the complete merging of two
binomial heaps.
function mergeTree(p, q)
if p.root <= q.root
return p.addSubTree(q)
else
return q.addSubTree(p)
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.
The operation of merging two heaps is perhaps the most
interesting and can be used as a subroutine in most other operations.
The lists of roots of both heaps are traversed simultaneously,
similarly as in the .
If only one of the heaps contains a tree of order j, this tree is moved to the merged heap. If both heaps contain a tree of order j, the two trees are merged to one tree of order j+1
so that the minimum-heap property is satisfied. Note that it may later
be necessary to merge this tree with some other tree of order j+1
present in one of the heaps. In the course of the algorithm, we need to
examine at most three trees of any order (two from the two heaps we
merge and one composed of two smaller trees).
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 log n and therefore the running time is O(log n).
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)
else
heap.addTree(tree)
heap.next() p.next() q.next()
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.
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 in O(log n) time.
Find minimum
To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can again be done easily in O(log n) time, as there are just O(log n) trees and hence 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 O(1). The pointer must be updated when performing any operation other than Find minimum. This can be done in O(log n) without raising the running time of any operation.
Delete minimum
To delete the minimum element from the heap, first find this
element, remove it from its binomial tree, and obtain a list of its
subtrees. Then transform this list of subtrees into a separate binomial
heap by reordering them from largest to smallest order. Then merge this
heap with the original heap.
function deleteMin(heap)
min = heap.trees().first()
for each current in heap.trees()
if current.root < min then min = current
for each tree in min.subTrees()
tmp.addTree(tree)
heap.removeTree(min)
merge(heap, tmp)
Decrease key
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 log n, so this takes O(log n) time.
Delete
To delete an element from the heap, decrease its key to minus
infinity (that is, some value lower than any element in the heap) and
then delete the minimum in the heap.
Performance
All of the following operations work in (log n) time on a binomial heap with n elements:
- Insert a new element to the heap
- Find the element with minimum key
- Delete the element with minimum key from the heap
- Decrease key of a given element
- Delete given element from the heap
- Merge two given heaps to one heap
Finding the element with minimum key can also be done in O(1) by using an additional pointer to the minimum.
See also
References
- , , , and . , Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 19: Binomial Heaps, pp.455–475.
- Vuillemin, J. (1978). Communications of the ACM 21, 309-314.
External links
- (a generic one and one optimized for integer keys)