NIST

binomial heap

(data structure)

Definition: A heap made of a forest of binomial trees with the heap property numbered k=0, 1, 2, …, n, each containing either 0 or 2k nodes. Each tree is formed by linking two of its predecessors, by joining one at the root of the other. The operations of insert a value, decrease a value, delete a value, and merge or join (meld) two queues take O(log n) time. The find minimum operation is a constant Θ(1).

Generalization (I am a kind of ...)
heap.

Aggregate parent (I am a part of or used in ...)
priority queue, Dijkstra's algorithm.

Aggregate child (... is a part of or used in me.)
binomial tree.

See also Fibonacci heap.

Note: Binomial heaps are so called because the number of nodes at each level of each subtree is a binomial coefficient. Sometimes called a binomial queue. After LK.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 26 May 2011.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "binomial heap", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 26 May 2011. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/binomialheap.html