heap
1. <programming> 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. <programming> 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)
Nearby terms:
head normalisation theorem « heads down «
head-strict «
heap » heartbeat » heatseeker » heat sink
|
