Binomial heap
In computer science, a binomial heap is a data structure similar to binary heap but also supporting the operation of merging two heaps. 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
| Table of contents |
|
2 Structure of a binomial heap 3 Implementation of the operations 4 References 5 External links |
Binomial tree
Binomial heap is implemented as a collection of binomial treess (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).
Structure of a binomial heap
Binomial heap is implemented as a set of binomial trees that satisfy binomial heap properties:
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 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.
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 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,
Implementation of the operations
References
External links