heap

1. programming An area of memory used for dynamic memoryallocation 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)