NIST

heap

(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

Implementation

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 14 December 2010.
HTML page formatted Mon Nov 18 10:44:09 2013.

Cite this as:
Chris L. Kuszmaul, "heap", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 December 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/heap.html