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 ...)
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.)
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.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 26 May 2011.
HTML page formatted Thu May 26 15:59:49 2011.
Cite this as:
Paul E. Black, "binomial heap", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/binomialheap.html