(data structure)
Definition: A complete binary tree where every node has a key more extreme (greater or less) than or equal to the key of its parent.
Generalization (I am a kind of ...)
complete binary tree, heap, k-ary heap with k=2.
Specialization (... is a kind of me.)
treap.
Aggregate parent (I am a part of or used in ...)
build-heap, heapify, heapsort, priority queue.
Aggregate child (... is a part of or used in me.)
array.
See also Fibonacci heap, binomial heap.
Note: Insertion is O(log2 n) where n is the number of nodes. A binary heap can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with one-based indexing. If a child index is greater than the number of nodes, the child does not exist.
The above implementation is inefficient with virtual memories because (almost) every level is in a different page. B-heaps allocate subtrees to a single page for better virtual memory performance.
Merging two binary heaps is O(n): the best you can do is just concatenate two heap arrays and make a heap of the result. Two binomial heaps can be merged in O(ln n). Two Fibonacci heaps can be merged in Θ(1).
Author: CLK
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 26 May 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Chris L. Kuszmaul, "binary 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/binaryheap.html