Binomial heap
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a binomial heap is a
data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
that acts as a
priority queue In computer science, a priority queue is an abstract data type similar to a regular queue (abstract data type), queue or stack (abstract data type), stack abstract data type. In a priority queue, each element has an associated ''priority'', which ...
. 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 A binary heap is a heap (data structure), heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964 as a data structure fo ...
but using a special tree structure that is different from the
complete binary tree In computer science, a binary tree is a Tree (data structure), tree data structure in which each node has at most two child node, children, referred to as the ''left child'' and the ''right child''. That is, it is a m-ary tree, ''k''-ary tree wi ...
s 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 In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...
(compare with a
binary heap A binary heap is a heap (data structure), heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964 as a data structure fo ...
, which has a shape of a single
binary tree In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...
), which are defined recursively as follows: * A binomial tree of order 0 is a single node * A binomial tree of order k has a root node whose children are roots of binomial trees of orders k-1, k-2, ..., 2, 1, 0 (in this order). A binomial tree of order k has 2^k nodes, and height k. The name comes from the shape: a binomial tree of order k has \tbinom k d nodes at depth d, a
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
. Because of its structure, a binomial tree of order k can be constructed from two trees of order k-1 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 be at most one binomial tree for each order, including zero order. 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 nodes consists of at most 1+\log_2 n binomial trees, where \log_2 is the
binary logarithm In mathematics, the binary logarithm () is the exponentiation, power to which the number must be exponentiation, raised to obtain the value . That is, for any real number , :x=\log_2 n \quad\Longleftrightarrow\quad 2^x=n. For example, th ...
. The number and orders of these trees are uniquely determined by the number of nodes n: there is one binomial tree for each nonzero bit in the
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two values (0 and 1) for each digit * Binary function, a function that takes two arguments * Binary operation, a mathematical op ...
representation of the number n. For example, the decimal number 13 is 1101 in binary, 2^3 + 2^2 + 2^0, and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see figure below). The number of different ways that n items with distinct keys can be arranged into a binomial heap equals the largest odd divisor of n!. For n=1,2,3,\dots these numbers are :1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... If the n 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 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
, 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 In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...
; 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 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 Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting ...
, 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, this tree is moved to the output heap. When both of the two 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. It may later become necessary to merge this tree with some other tree of order j+1 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(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 \log_2 n and therefore the running time is O(\log n).


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 O(\log n). 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 k consecutive insertions, the total time for the insertions is O(k+\log n). Another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive insert has an ''amortized'' time of O(1) (i.e. constant) per insertion. A variant of the binomial heap, the
skew binomial heap In computer science, a skew binomial heap (or skew binomial queue) is a data structure for priority queue operations. It is a variant of the binomial heap that supports constant-time insertion operations in the worst case, rather than amortized ...
, achieves constant worst case insertion time by using forests whose tree sizes are based on the
skew binary number system The skew binary number system is a non-standard positional numeral system in which the ''n''th digit contributes a value of 2^ - 1 times the digit (digits are indexed from 0) instead of 2^ times as they do in binary. Each digit has a value of 0, ...
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 O(\log n) time, as there are just O(\log n) 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 O(1). The pointer must be updated when performing any operation other than finding the minimum. This can be done in O(\log n) 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 (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 \log_2 n children, creating this new heap takes time O(\log n). Merging heaps takes time O(\log n), so the entire delete minimum operation takes time O(\log n). 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)


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_2 n, so this takes O(\log n) time. However, this operation requires that the representation of the tree include pointers from each node to its parent in the tree, somewhat complicating the implementation of other operations.


Delete

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.


Summary of running times


Applications

*
Discrete event simulation A discrete-event simulation (DES) models the operation of a system as a (discrete) sequence of events in time. Each event occurs at a particular instant in time and marks a change of state in the system. Between consecutive events, no change in th ...
*
Priority queue In computer science, a priority queue is an abstract data type similar to a regular queue (abstract data type), queue or stack (abstract data type), stack abstract data type. In a priority queue, each element has an associated ''priority'', which ...
s


See also

* Weak heap, a combination of the binary heap and binomial heap data structures


References


External links


Two C implementations of binomial heap
(a generic one and one optimized for integer keys)


Common Lisp implementation of binomial heap
{{Data structures Heaps (data structures)