binary heap

(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(log₂ 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.

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

Implementation

delete (C) and insert (C and Pascal) both of which use the auxiliary function siftup (C and Pascal), explanation, examples, and code (C). (Fortran)

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

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

Entry modified Thu Oct 27 09:59:50 2005.
HTML page formatted Thu Oct 27 10:13:08 2005.

Cite this as:
Chris L. Kuszmaul, "binary heap", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/binaryheap.html