(data structure)

Definition: A complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap.

Generalization (I am a kind of ...)
complete tree.

Specialization (... is a kind of me.)
binary heap, k-ary heap, binomial heap, Fibonacci heap.

Aggregate parent (I am a part of or used in ...)
heapsort, priority queue.

Aggregate child (... is a part of or used in me.)
heap property.

Note: Speaking about operating systems, "heap" refers to memory from which chunks can be allocated.

Author: CLK


Bro. David Carlson's heaps and heapsort tutorial and code (C++).

More information

B-heaps allocate subtrees to a single page for better virtual memory performance.

J. W. J. Williams, Algorithm 232 Heapsort, CACM, 7(6):378-348, June 1964.

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 11 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Chris L. Kuszmaul, "heap", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 11 February 2019. (accessed TODAY) Available from: