heap
1.
An area of memory used for {dynamic memory allocation} where blocks of memory are allocated and freed in
an arbitrary order and the pattern of allocation and size of
blocks is not known until {run-time}. Typically, a program
has one heap which it may use for several different purposes.
Heap is required by languages in which functions can return
arbitrary data structures or functions with {free variables}
(see {closure}). In {C} functions {malloc} and {free} provide
access to the heap.
Contrast {stack}. See also {dangling pointer}.
2.
A data structure with its elements partially ordered (sorted) such that finding either the minimum or the
maximum (but not both) of the elements is computationally
inexpensive (independent of the number of elements), while
both adding a new item and finding each subsequent
smallest/largest element can be done in O(log n) time, where n
is the number of elements.
Formally, a heap is a {binary tree} with a key in each {node},
such that all the {leaves} of the tree are on two adjacent
levels; all leaves on the lowest level occur to the left and
all levels, except possibly the lowest, are filled; and the
key in the {root} is at least as large as the keys in its
children (if any), and the left and right subtrees (if they
exist) are again heaps.
Note that the last condition assumes that the goal is finding
the minimum quickly.
Heaps are often implemented as one-dimensional {arrays}.
Still assuming that the goal is finding the minimum quickly
the {invariant} is
heap[i] <◦ heap[2▫i] and heap[i] <◦ heap[2▫i:1] for all i,
where heap[i] denotes the i-th element, heap[1] being the
first. Heaps can be used to implement {priority queues} or in
{sort} algorithms.
(1996-02-26)