Binomial heap
|
|
- For other topics using the name "binomial", see binomial (disambiguation).
In computer science, a binomial heap is a data structure similar to binary heap but also supporting the operation of merging two heaps quickly. All of the following operations work in O(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
Thus binomial heap is an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation.
| Contents |
Binomial tree
Binomial heap is implemented as a collection of binomial trees (compare with a binary heap, which has a shape of a single binary tree). Binomial tree is defined recursively:
- Binomial tree of order 0 is a single node
- Binomial tree of order k has a root of degree k and its children are roots of binomial trees of orders k-1, k-2, ..., 2, 1, 0 (in this order).
Binomial tree of order k can also be constructed from two trees of order k-1 by attaching one of them as the leftmost child of the other one. Binomial tree of order k has 2k nodes, height k.
Variants of binomial trees are also used to construct other heap data structures such as Fibonacci heaps and soft heaps.
Structure of a binomial heap
Binomial heap is implemented as a set of binomial trees that satisfy binomial heap properties:
- Each binomial tree in the heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent.
- For any non-negative integer j, there is at most one binomial tree of order j.
The first property tell us that the root of each binomial tree contains the smallest key in the tree. The second property implies that a binomial heap with n elements consists of at most lg n + 1 binomial trees. In fact, the number and orders of these trees is uniquely determined by the number of elements n: each binomial tree corresponds to digit one in the binary representation of number n. For example number 13 is 1101 in binary, <math>2^3 + 2^2 + 2^0<math>, and thus the binomial heap with 13 elements will consist of three binomial trees of orders 3, 2, and 0 (see figure below).
The roots of the binomial trees are kept in a linked list ordered by increasing order of the tree.
Example of a binomial heap containing elements with keys 1,2,...,13. The heap consists of three binomial trees with orders 0, 2, and 3.
Implementation of the operations
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 merge algorithm. 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 we may later need 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). Each tree has order at most lg n and therefore the running time is O(lg n).
To insert a new element to a heap we simply create a new heap containing only this element and then merge it with the original heap in O(lg n) time.
To find the minimum element of the heap, we only need to find minimum among the roots of the binomial trees. This can again be done easily in O(lg n) time.
To delete the minimum element from the heap, we first find this element, remove it from its binomial tree, obtaining a list of its subtrees. We transform this list of subtrees into a separate binomial heap by reordering them from largest to smallest order. Then we merge this heap with the original heap.
When we decrease a key of an element, it may become smaller than the key of its parent, violating the minimum-heap property. If this is the case, we 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 lg n, so this takes O(lg n) time.
To delete an element from the heap, we may 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,
References
- Cormen, T. H.; Leiserson C. E.; & Rivest R. L. (1990) Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8
- Vuillemin, J. (1978). A data structure for manipulating priority queues. (http://portal.acm.org/citation.cfm?id=359478) Communications of the ACM 21, 309-314.
External links
- Java applet simulation of binomial heap (http://www.cs.yorku.ca/~aaw/Sotirios/BinomialHeap.html)de:Binomial-Heap