Binomial heap

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, a binomial heap is a data structure that acts as a priority queue. 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 but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

In computer science, a binomial heap is a data structure that acts as a priority queue. 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 but using a special tree structure that is different from the complete binary trees used by binary heaps.

Binomial heaps were invented in 1978 by Jean Vuillemin. 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. if p.root.key 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) . 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)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1221086681 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.