heap


Also found in: Dictionary, Thesaurus, Legal, Acronyms, Idioms, Wikipedia.

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 ?
Monseigneur, there are so many little heaps of poor grass?
Long ago the heap of coins had become too large for the iron pot to hold them, and he had made for them two thick leather bags, which wasted no room in their resting-place, but lent themselves flexibly to every corner.
The day passed slowly, and with the evening came the little mouse and said, 'Now there is not a single stalk of corn left in any field; they are all collected in one big heap on the hill out there.
That heap of stones brings us at once to the dawn of the Anglian kingdom.
When the Wicked Witch looked out again and saw all her crows lying in a heap, she got into a terrible rage, and blew three times upon her silver whistle.
Round went the wheel again to the old song, and the manikin once more spun the heap into gold.
From the moment Pierre had witnessed those terrible murders committed by men who did not wish to commit them, it was as if the mainspring of his life, on which everything depended and which made everything appear alive, had suddenly been wrenched out and everything had collapsed into a heap of meaningless rubbish.
Outside the entrance to this rock heap the guide gave a low wail that sounded like "Lee-ow-ah
One morning early, we had scratched out of the wall quite a heap of fragments.
A very little boy stood upon a heap of gravel for the honor of Rum Alley.
The Fox accumulated all that they had killed into one large heap and left to himself the smallest possible morsel.
One looked like a small heap of glittering broken glass.