HOME
The Info List - Binomial Heap


--- Advertisement ---



(i) (i) (i) (i)

In computer science , a BINOMIAL HEAP is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap ), which is a priority queue supporting merge operation.

CONTENTS

* 1 Binomial heap
Binomial heap
* 2 Structure of a binomial heap

* 3 Implementation

* 3.1 Merge * 3.2 Insert * 3.3 Find minimum * 3.4 Delete minimum * 3.5 Decrease key * 3.6 Delete

* 4 Summary of running times * 5 Applications * 6 See also * 7 References * 8 External links

BINOMIAL HEAP

A binomial heap is implemented as a collection of BINOMIAL TREES (compare with a binary heap , which has a shape of a single binary tree ), 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).

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 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.

The name comes from the shape: a binomial tree of order n {displaystyle n} has ( n d ) {displaystyle {tbinom {n}{d}}} nodes at depth d {displaystyle d} . (See Binomial coefficient .)

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 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 nodes consists of at most log n + 1 binomial trees. In fact, the number and orders of these trees are uniquely determined by the number of nodes n: each binomial tree corresponds to one digit in the binary representation of number n. For example number 13 is 1101 in binary, 2 3 + 2 2 + 2 0 {displaystyle 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). Example of a binomial heap containing 13 nodes 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 linked list , ordered by increasing order of the tree.

MERGE

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.

As mentioned above, the simplest and most important operation is the merging of two binomial trees of the same order within a binomial heap. 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 becomes 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.key log n ) , {displaystyle Omega (log log n),} upper bound of O ( 2 2 log log n ) . {displaystyle O(2^{2{sqrt {log log n}}}).} * ^ n is the size of the larger heap.

APPLICATIONS

* Discrete event simulation * Priority queues

SEE ALSO

* Fibonacci heap
Fibonacci heap
* Skew binomial heap * Soft heap * Weak heap , an implicit variant of the binomial heap

REFERENCES

* Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) . "Chapter 19: Binomial Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 455–475. ISBN 0-262-03293-7 . * Vuillemin, Jean (April 1978). "A data structure for manipulating priority queues" (PDF). Communications of the ACM . 21 (4): 309–314. CiteSeerX 10.1.1.309.9090  . doi :10.1145/359460.359478 .

EXTERNAL

.