heap

(redirected from heaped)
Also found in: Dictionary, Thesaurus, Legal, Idioms.

heap

(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.

heap

(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.

heap

In programming, it refers to a common pool of memory that is available to the program. The management of the heap is either done by the applications themselves, allocating and deallocating memory as required, or by the operating system or other system program.
References in classic literature ?
The lodge at the entrance was uninhabited, and the gates stood open, with dust and fallen leaves heaped up against them.
Skeletons and skulls by the hundred were heaped against the wall of the church, held in position by a wire that left the whole gruesome stack visible.
In ne house was a father weeping for the loss of his daughter, in another perhaps a mother trembling for the fate of her child; and instead of the blessings that had formerly been heaped on the Sultan's head, the air was now full of curses.
For, occupied incessantly with the consideration of the limits prescribed to their power by nature, they became so entirely convinced that nothing was at their disposal except their own thoughts, that this conviction was of itself sufficient to prevent their entertaining any desire of other objects; and over their thoughts they acquired a sway so absolute, that they had some ground on this account for esteeming themselves more rich and more powerful, more free and more happy, than other men who, whatever be the favors heaped on them by nature and fortune, if destitute of this philosophy, can never command the realization of all their desires.
I turned without further word and sought out Tars Tarkas, to whom I vehemently objected to the unnecessary humiliations and cruelties, as they seemed to my lover's eyes, that were being heaped upon Dejah Thoris.