Longman Dictionary of Contemporary English
Heap (data structure)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).
In a heap, the highest (or lowest) priority element is always stored at the root. A heap is not a sorted structure and can be regarded as partially ordered. As visible from the heap-diagram, there is no particular relationship among nodes on any given level, even among the siblings. When a heap is a complete binary tree, it has a smallest possible height—a heap with N nodes always has log N height. A heap is a useful data structure when you need to remove the object with the highest (or lowest) priority.
Note that, as shown in the graphic, there is no implied ordering between siblings or cousins and no implied sequence for an in-order traversal (as there would be in, e.g., a binary search tree). The heap relation mentioned above applies only between nodes and their parents, grandparents, etc. The maximum number of children each node can have depends on the type of heap, but in many types it is at most two, which is known as a binary heap.
The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact priority queues are often referred to as "heaps", regardless of how they may be implemented.
A heap data structure should not be confused with the heap which is a common name for the pool of memory from which dynamically allocated memory is allocated. The term was originally used only for the data structure.
Heap may refer to:
Heap is a surname. Notable people with the surname include
- Brian Heap, British biologist
- Dan Heap, Canadian politician
- David Porter Heap, American engineer
- Imogen Heap, British singer-songwriter
- John Heap, British geographer
- Mark Heap, British actor
- Todd Heap, American football player
- Tom Heap, British television and radio reporter and presenter
The Heap is the name of several fictional comic book muck- monsters, the original of which first appeared in Hillman Periodicals' Air Fighters Comics #3 (Dec. 1942), during the period fans and historians call the Golden Age of Comic Books. The character was created by writer Harry Stein and artist Mort Leav, and revived in the 1980s by Eclipse Comics.
Similar but unrelated characters appeared in comics stories published by Skywald in the 1970s and Image Comics in the 1990s.
In abstract algebra, a heap (sometimes also called a groud) is a mathematical generalization of a group. Informally speaking, a heap is obtained from a group by "forgetting" which element is the unit, in the same way that an affine space can be viewed as a vector space in which the 0 element has been "forgotten". A heap is essentially the same thing as a torsor, and the category of heaps is equivalent to the category of torsors, with morphisms given by transport of structure under group homomorphisms, but the theory of heaps emphasizes the intrinsic composition law, rather than global structures such as the geometry of bundles.
Formally, a heap is an algebraic structure consisting of a non-empty setH with a ternary operation denoted [x, y, z] ∈ H that satisfies
- the para-associative law
- the identity law
A group can be regarded as a heap under the operation [x, y, z] = xyz. Conversely, let H be a heap, and choose an element . The binary operationx * y = [x, e, y] makes H into a group with identitye and inverse x = [e, x, e]. A heap can thus be regarded as a group in which the identity has yet to be decided.
Whereas the automorphisms of a single object form a group, the set of isomorphisms between two isomorphic objects naturally forms a heap, with the operation [f, g, h] = fgh (here juxtaposition denotes composition of functions). This heap becomes a group once a particular isomorphism by which the two objects are to be identified is chosen.
The Collaborative International Dictionary
Heap \Heap\, v. t. [imp. & p. p. Heaped (h[=e]pt); p. pr. & vb. n. Heaping.] [AS. he['a]pian.]
To collect in great quantity; to amass; to lay up; to accumulate; -- usually with up; as, to heap up treasures.
Though he heap up silver as the dust.
--Job. xxvii. 16.
To throw or lay in a heap; to make a heap of; to pile; as, to heap stones; -- often with up; as, to heap up earth; or with on; as, to heap on wood or coal.
To form or round into a heap, as in measuring; to fill (a measure) more than even full.
Heap \Heap\ (h[=e]p), n. [OE. heep, heap, heap, multitude, AS. he['a]p; akin to OS. h[=o]p, D. hoop, OHG. houf, h[=u]fo, G. haufe, haufen, Sw. hop, Dan. hob, Icel. h[=o]pr troop, flock, Russ. kupa heap, crowd, Lith. kaupas. Cf. Hope, in Forlorn hope.]
A crowd; a throng; a multitude or great number of persons.
The wisdom of a heap of learned men.
A heap of vassals and slaves.
He had heaps of friends.
A great number or large quantity of things not placed in a pile; as, a heap of trouble. [Now Low or Humorous]
A vast heap, both of places of scripture and quotations.
I have noticed a heap of things in my life.
--R. L. Stevenson.
A pile or mass; a collection of things laid in a body, or thrown together so as to form an elevation; as, a heap of earth or stones.
Huge heaps of slain around the body rise.
(often followed by `of') a large number or amount or extent; "a batch of letters"; "a deal of trouble"; "a lot of money"; "he made a mint on the stock market"; "it must have cost plenty" [syn: batch, deal, flock, good deal, great deal, hatful, lot, mass, mess, mickle, mint, muckle, peck, pile, plenty, pot, quite a little, raft, sight, slew, spate, stack, tidy sum, wad, whole lot, whole slew]
n. 1 A crowd; a throng; a multitude or great number of people. 2 A pile or mass; a collection of things laid in a body, or thrown together so as to form an elevation. 3 A great number or large quantity of things. 4 (context computing English) A data structure consisting of trees in which each node is greater than all its children. 5 (rfdef: English) vb. 1 (context transitive English) To pile in a heap. 2 (context transitive English) To form or round into a heap, as in measuring. 3 (context transitive English) To supply in great quantity.
Douglas Harper's Etymology Dictionary
Old English heap "pile, great number, multitude" (of things or persons), from West Germanic *haupaz (cognates: Old Saxon hop, Old Frisian hap, Middle Low German hupe, Dutch hoop, German Haufe "heap"), perhaps related to Old English heah "high." Slang meaning "old car" is attested from 1924. As a characteristic word in American Indian English speech, "a lot, a great deal," by 1832.
Old English heapian "collect, heap up, bring together;" from heap (n.). Related: Heaped; heaping. Compare Old High German houfon "to heap."
Usage examples of "heap".
We had just settled down to our tucker when one of the abos came up smiling and handed me a slab of bark heaped with some kind of native food.
Many towns and villages of Thrace were already evacuated: a heap of ruins marked the place of Philippopolis, and a similar calamity was expected at Demotica and Adrianople, by the first authors of the revolt.
The Virgin Mary was there in the form of Our Lady of Carmel, standing in for Ezilie, a goddess of Voodoo, with heaps of flowers at her feet and perhaps the most candles before her, all of them aflicker in their deep glasses as a breeze stirred the room.
In fact, looking at the unspeaking men draped as best they could over the afterbody of the car, and the dead Invaders lying heaped to one side, and the blood all over everything, and Newsted and the others standing next to the gun-carrier, staring at Mrs.
The airdrome had been bombed eight months before, and knobby slabs of white stone rubble had been bulldozed into flat-topped heaps on both sides of the entrance through the wire fence surrounding the field.
This bank consists of alluvia, or large heaps of organic matter, brought either from the Equator by the Gulf Stream, or from the North Pole by the counter-current of cold water which skirts the American coast.
Chinese Classics in gold upon them, and the large establishment, show that the family belongs to the upper class of Anamites, and leave one quite unprepared for the reeking, festering heap of garbage below the house, the foul, fetid air, and swarming vermin of the interior, and the unwashedness of the inmates.
Gin, vodka, aquavit, Chablis and hock, arrak and Calvados heaped six feet high on one side.
Us raked out hot ashes den and cooked good old ashcakes what was a heap better for us dan dis bread us buys from de stores now.
Then, too, there was the upsetting of the larder, the disappearance of certain staples, and the jarringly comical heap of tin cans pried open in the most unlikely ways and at the most unlikely places.
She pulled off her torn blouse looking at it with disgust, it along with the rest of her garments were thrown into a tangled heap upon the Aubusson rug beside her bed.
Two automata, circa 1840, German, brothers, sat at facing desks heaped high with manuscripts, books, old shirts, astrolabes, maps, and ink-stands.
The volcano had awoke, and the vapor had penetrated the mineral layer heaped at the bottom of the crater.
As regards the soil, the gullies at Anzac on the spurs of Sari Bahr were quite bewildering in their heaped up confusion, partly rocky, but mainly a sort of red clay and very steep.
He had learned how to enjoy being on top of the heap, and when he was between bands, he was content to earn a good living playing sessions or acting as a side-man on tours, helping to fill up the musical sound without getting in the way of the current stars.