heap


Also found in: Dictionary, Thesaurus, 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 ?
As the road-mender plied his dusty labour, and the hail-clouds, rolling away, revealed bright bars and streaks of sky which were responded to by silver gleams upon the landscape, the little man (who wore a red cap now, in place of his blue one) seemed fascinated by the figure on the heap of stones.
The Wicked Witch was so angry when she saw her black bees in little heaps like fine coal that she stamped her foot and tore her hair and gnashed her teeth.
Her bees and her crows and her wolves were lying in heaps and drying up, and she had used up all the power of the Golden Cap; but if she could only get hold of the Silver Shoes, they would give her more power than all the other things she had lost.
Hogs and poee-poee were baking in numerous ovens, which, heaped up with fresh earth into slight elevations, looked like so many ant-hills.
Whilst he was doing this,I caught sight of a knot of young lasses, who were sitting near us on the grass surrounded by heaps of flowers which they were forming into garlands.
The program began in 2012 and was conducted at a purpose-built, small-scale heap leach facility at Wingfield run by Bureau Veritas, under direction from BHP and with support from the South Australian Government.
James Heaps , an obstetrician-gynecologist who had been working at UCLA part-time since 1983.
Following that announcement, gold recovery from the leach pad increasingly exceeded expectations, and the company then focused test work and analysis on the viability of resuming mining and heap leaching.
Heap, 43, was jailed for nine years in September for attempting to sneak the illicit haul into the Fazakerley prison as he entered work.
The letter said the three boys dumped the body under a garbage heap in Siraj Town.
On his home green, Heap beat his Yorkshire Junior teammate Callum Wadsworth of Shepley in the final, but the 21-1 scoreline was something of a surprise.
Mwingi West MP Charles Nguna and Kitui woman representative Irene Kasalu yesterday afternoon took journalist to the scene to show them the heap only to find it had just been flattened.