Heap
In computer science, a heap is a tree-based data structure, specifically a complete binary tree that satisfies the heap property, where for any given node, the value of the parent is either greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the values of its children. The term "heap" has other meanings in mathematics and general usage, covered in later sections.[1][2] Heaps are typically implemented using an array for efficient storage, with the root at index 1, left child at 2i, and right child at 2i+1, allowing representation without explicit pointers. The height of a heap with n elements is floor(log n), enabling logarithmic time for key operations.[1]
Heaps support fundamental operations such as insertion, which adds an element at the end and "swims" it up to restore the heap property in O(log n) time, and extraction of the maximum (or minimum), which removes the root, replaces it with the last element, and "sinks" it down in O(log n) time.[2] Building a heap from an unsorted array of n elements can be done in O(n) time by applying heapify operations bottom-up on non-leaf nodes.[1] These efficient operations make heaps ideal for implementing priority queues, where elements are dequeued based on priority rather than insertion order.[3]
Beyond priority queues, heaps find extensive applications in algorithms, including heapsort—an in-place sorting algorithm that achieves O(n log n) time complexity by repeatedly extracting the maximum element—and graph algorithms like Dijkstra's shortest path, where a min-heap prioritizes nodes by distance.[2] They are also used in job scheduling systems, such as CPU task management, to select the highest-priority process in O(log n) time,[4] and in network optimization for handling packets or events.[5] Variations like Fibonacci heaps extend these capabilities for even faster amortized performance in certain decrease-key operations, though binary heaps remain the most commonly used due to their simplicity.
In computing
Heap data structure
A heap is a specialized tree-based data structure consisting of a complete binary tree that satisfies the heap property. In a max-heap, the value of each parent node is greater than or equal to the values of its children, ensuring the maximum value resides at the root. In a min-heap, the parent node value is less than or equal to its children's values, placing the minimum at the root. This structure enables efficient priority-based operations, distinguishing it from other tree structures like binary search trees.[6][7]
Heaps are typically represented as arrays for space efficiency and fast access, avoiding explicit pointers. In a 1-based array indexing scheme, the root is at index 1; for any node at index i > 1, its parent is at \lfloor i/2 \rfloor, left child at $2i, right child at $2i + 1. This mapping preserves the complete binary tree shape, with the array filling level by level from left to right (indices 1 to n), allowing heap operations to traverse implicitly via index calculations.[6]
Key operations on a heap maintain the heap property while achieving logarithmic or linear time complexities. Finding the maximum (or minimum) is O(1), simply accessing the root. Insertion adds the new element at the end of the array and "bubbles up" by swapping with its parent if the heap property is violated, taking O(\log [n](/page/N+)) time. Extraction of the maximum (or minimum) removes the root, replaces it with the last element, and "bubbles down" by swapping with the larger (or smaller) child until the property holds, also O(\log [n](/page/N+)). Building a heap from an unsorted array, known as heapify, starts from the bottom non-leaf nodes and applies bubble-down recursively upward, achieving O([n](/page/N+)) time overall rather than the naive O([n](/page/N+) \log [n](/page/N+)).[6][8]
Pseudocode for insertion into a max-heap (1-based indexing) is as follows:
procedure max-heap-insert(A, key)
A.heap-size = A.heap-size + 1
i = A.heap-size
A[i] = key
while i > 1 and A[parent(i)] < A[i]
swap A[i] with A[parent(i)]
i = parent(i)
procedure max-heap-insert(A, key)
A.heap-size = A.heap-size + 1
i = A.heap-size
A[i] = key
while i > 1 and A[parent(i)] < A[i]
swap A[i] with A[parent(i)]
i = parent(i)
Here, parent(i) = \lfloor i/2 \rfloor. For extraction:
procedure heap-extract-max(A)
if A.heap-size < 1
error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
max-heapify(A, 1)
return max
procedure max-heapify(A, i)
left = 2*i
right = 2*i + 1
if left ≤ A.heap-size and A[left] > A[i]
largest = left
else
largest = i
if right ≤ A.heap-size and A[right] > A[largest]
largest = right
if largest ≠ i
swap A[i] with A[largest]
max-heapify(A, largest)
procedure heap-extract-max(A)
if A.heap-size < 1
error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
max-heapify(A, 1)
return max
procedure max-heapify(A, i)
left = 2*i
right = 2*i + 1
if left ≤ A.heap-size and A[left] > A[i]
largest = left
else
largest = i
if right ≤ A.heap-size and A[right] > A[largest]
largest = right
if largest ≠ i
swap A[i] with A[largest]
max-heapify(A, largest)
(Note: Pseudocode uses 1-based indexing; max-heapify ensures the subtree rooted at i satisfies the property.)[6]
Heaps are fundamental for implementing priority queues, where elements are dequeued based on priority rather than insertion order, supporting efficient scheduling in algorithms like Dijkstra's shortest paths. Heapsort leverages the structure for in-place sorting: build a max-heap in O(n), then repeatedly extract the maximum and heapify the reduced heap, yielding O(n \log n) time overall. For median maintenance in streaming data, two heaps—a max-heap for the lower half and a min-heap for the upper half—are balanced to report the median in O(\log n) per insertion, with the median as the root of the larger heap or the average of both roots.[6][7][9]
The heap data structure was introduced by J. W. J. Williams in 1964 as part of the ALGOL implementation for heapsort, with the linear-time heapify procedure later refined by Robert W. Floyd in the same year.[7][8]
Dynamic memory heap
The dynamic memory heap is a region of a computer's memory dedicated to the allocation and deallocation of variable-sized blocks during program runtime, typically accessed through pointers returned by allocation functions.[10] Unlike fixed-size allocations, the heap allows programs to request memory of arbitrary sizes as needed, forming a large pool that grows or shrinks based on the operating system's capabilities and the program's demands.[11] This unorganized storage contrasts with more structured memory regions, enabling flexible handling of data structures like linked lists or dynamically sized arrays that persist beyond the scope of individual function calls.[12]
In contrast to the stack, which manages automatic allocation of fixed-size local variables in a last-in, first-out (LIFO) manner with deallocation handled implicitly upon function return, the heap supports explicit, programmer-controlled dynamic allocation.[13] Stack allocations are efficient and scoped to function lifetimes, making them suitable for temporary variables, but they cannot accommodate runtime-determined sizes or long-lived objects.[14] Heap allocations, however, survive function calls and require manual or automated freeing, providing greater flexibility at the cost of added management overhead.[11]
Heap allocation employs various algorithms to select and manage free blocks from the available pool, including first-fit, which scans the free list and allocates the first block large enough for the request; best-fit, which searches for the smallest suitable block to minimize waste; and the buddy system, which divides memory into power-of-two blocks for efficient splitting and coalescing.[15] These mechanisms are invoked through language-specific functions, such as malloc and free in C, which request and release raw bytes from the heap, or new and delete in C++, which additionally handle object construction and destruction.[16] In operating systems like Unix, the heap's boundaries are adjusted via system calls such as brk and sbrk, which set or increment the "program break" to extend the heap into unallocated memory.[17]
Management of the heap involves tracking allocated and free blocks using metadata, such as headers containing block size and allocation status, and sometimes footers for quick coalescing of adjacent free blocks.[18] In languages without manual deallocation, like Java and Python, garbage collection automates the detection and reclamation of unreachable objects on the heap, using techniques such as mark-and-sweep to identify live data and compact memory.[19] This process prevents dangling pointers but introduces pauses during collection cycles.[20]
Key challenges in heap management include external fragmentation, where free memory becomes scattered into small, unusable blocks despite sufficient total free space for a large request, and internal fragmentation, arising from allocating blocks larger than requested, wasting space within them.[21] Memory leaks occur when allocated blocks are not freed, leading to gradual exhaustion of available heap space over time.[22] For instance, in C programs, forgetting to call free after malloc can cause leaks, while best-fit algorithms may exacerbate internal fragmentation by leaving small remnants.[23]
The term "heap" evokes an image of a disorganized pile of items, reflecting the unstructured nature of this free store, and has been used in computing since at least the early 1970s, notably in the ALGOL 68 programming language report where it denoted dynamic storage allocation.[24]
Heap's algorithm
Heap's algorithm is an efficient recursive method for generating all possible permutations of n distinct objects, ensuring that each successive permutation is obtained from the previous one by a single interchange of two elements. This approach minimizes the number of element movements, making it particularly suitable for applications where permutations must be produced sequentially with minimal disruption, such as in optimization problems or exhaustive search algorithms. The algorithm operates on an array representing the objects, producing the n! permutations in a specific order without requiring additional storage for intermediate results beyond the recursion stack.[25]
The algorithm works by recursively generating permutations of the first k elements of the array (for k from n down to 1), with the base case outputting the current array when k=1. For a given k, it first recursively generates all (k-1)! permutations of the first k-1 elements while holding the k-th element fixed in position. Then, it performs a loop over i from 1 to k: after each recursive call on k-1, it swaps the k-th element with the i-th element if the parity dictates, but the swap logic is tailored to parity of k to ensure coverage of all positions without redundancy—specifically, for even k, the swaps cycle through positions 1 to k, while for odd k, the effective swap focuses on the last position in a way that complements the recursion. This parity-based swapping ensures that every possible placement of the k-th element is explored exactly once across the permutations of the remaining elements. After the loop, the recursion unwinds, restoring the array for higher levels.[25]
Here is the recursive pseudocode for Heap's algorithm (using 1-based indexing for the array A[1..n]):
procedure HeapPermute(A, k)
if k = 1 then
output A
else
HeapPermute(A, k-1)
for i = 1 to k do
if k mod 2 = 0 then
swap A[i] and A[k] // even k: swap with varying i
else
swap A[1] and A[k] // odd k: always swap with first position
HeapPermute(A, k-1)
end for
end if
end procedure
procedure HeapPermute(A, k)
if k = 1 then
output A
else
HeapPermute(A, k-1)
for i = 1 to k do
if k mod 2 = 0 then
swap A[i] and A[k] // even k: swap with varying i
else
swap A[1] and A[k] // odd k: always swap with first position
HeapPermute(A, k-1)
end for
end if
end procedure
Note that the initial call is HeapPermute(A, n), and the swaps are performed after each recursive call on k-1 but before the next, with the parity determining the fixed or varying swap partner to generate distinct permutations. This structure ensures no backtracking swaps are needed beyond the generation step.[25]
In terms of efficiency, the algorithm performs exactly (n! - 1) swaps in total across all permutations, as each new permutation after the first is produced by a single swap, minimizing computational overhead for element rearrangements. The overall time complexity is O(n \cdot n!), dominated by the need to output or process each of the n! permutations, each requiring O(n) time to copy or examine; the space complexity is O(n) due to the recursion depth. This makes it more efficient than naive recursive backtracking methods, which can involve up to O(n) swaps per permutation.[26][25]
The algorithm was proposed by Australian mathematician B. R. Heap in 1963 as part of his work on permutation generation via interchanges, published in The Computer Journal. It was later praised by Robert Sedgewick in 1977 for its simplicity and speed in recursive exchange-based methods, noting its superiority over contemporaries like the Johnson-Trotter algorithm in terms of minimal instructions per permutation on typical hardware.[25][26]
The minimal swap property arises because the algorithm constructs each permutation by disturbing only two elements from the prior one, leveraging the recursive structure to systematically explore all positions for the current element without redundant rearrangements or full array copies. This contrasts with lexicographic generation methods that may require shifting multiple elements.[25][26]
For practical implementation, a non-recursive version can be derived using an array of counters c[1..n] to simulate the recursion stack, where each c tracks the number of times the i-th level has been "swapped," initializing c=1 for i=2 to n. The procedure loops through levels, performing swaps based on parity (swap with position 1 if i odd, else with c) and incrementing counters until all permutations are exhausted, outputting after each swap. This avoids recursion overhead and is useful for large n where stack space is limited, though still bounded by n! output size.[26]
In mathematics
Algebraic heap
In algebra, a heap is defined as a non-empty set H equipped with a ternary operation [x, y, z] : H^3 \to H. This operation satisfies two key axioms: para-associativity, expressed as [[a, b, c], d, e] = [a, [b, c, d], e] = [a, b, [c, d, e]] for all a, b, c, d, e \in H, and the biunitary condition, which states that every element h \in H acts as a unit in the sense that [h, h, k] = k = [k, h, h] for all k \in H. These axioms ensure the structure captures a form of generalized associativity without requiring a binary operation or distinguished identity element.[27]
The concept of the heap was introduced by Anton Sushkevich in his 1937 work Theory of Generalized Groups, where the term derives from the Russian word "груда" (gruda), meaning "pile" or "heap," reflecting an analogy to unordered collections in algebraic generalizations of groups. Earlier contributions to similar ternary structures appeared in the 1920s by mathematicians such as Heinz Prüfer and Reinhold Baer, but Sushkevich formalized the heap as a foundational object in the theory of generalized groups.
Heaps are closely related to groups, as every group G induces a heap structure on itself via the operation [x, y, z] = x y^{-1} z, effectively "forgetting" the identity element while preserving the underlying group law. Conversely, given a heap H, selecting any base point e \in H allows recovery of a group structure on H by defining a binary operation x * y = [x, e, y], where e serves as the identity; different choices of base point yield isomorphic groups acting transitively on H.[27] This equivalence positions heaps as torsors under group actions, where the category of heaps is isomorphic to the category of pairs consisting of a group and a principal homogeneous space (torsor) for that group.[27]
Representative examples include the integers \mathbb{Z} under the operation [x, y, z] = x - y + z, which arises from the additive group structure and corresponds to affine transformations preserving differences. More generally, any group-derived heap takes the form [x, y, z] = x y^{-1} z. Heaps can also be constructed from quasigroups that are idempotent, meaning they satisfy x \cdot x = x for a derived binary operation, leading to ternary structures via isotopy classes.[28] Additionally, heaps arise naturally as torsors in group actions, such as affine spaces over a vector space, where the ternary operation encodes the parallelogram law for vector differences.
Properties and relations to other structures
Every algebraic heap is a principal homogeneous space, or torsor, over its associated structure group, which arises naturally from the ternary operation by fixing a base point to recover the group action. Specifically, for a heap (H, [-,-,-]), the structure group \mathrm{Str}(H) acts transitively and freely on H, making H a G-torsor for G = \mathrm{Str}(H).[27] This torsor structure highlights how heaps capture group-like behavior without a distinguished identity, with biunitary elements enabling the definition of left and right multiplications that mimic group operations.[29]
Heaps are closely related to quasigroups, particularly as idempotent quasigroups equipped with an associative ternary operation. A heap induces a quasigroup structure via the binary operation defined relative to a fixed element, and conversely, not every idempotent quasigroup yields a heap, as the latter requires the para-associative property of the ternary operation.[29] For instance, heaps correspond to right solvable Ward quasigroups, which are idempotent and satisfy additional solvability conditions ensuring the existence of unique solutions to equations like [x, y, z] = w.[29]
Any heap embeds into an involuted semigroup, where the ternary operation extends naturally from the semigroup's binary structure via [a, b, c] = a b^{-1} c, with the involution providing the necessary inverses. Furthermore, imposing the principal congruence—equating elements that differ by the action of the structure group—yields a quotient that is isomorphic to the associated group.[27]
Illustrative examples underscore these relations. Starting from the cyclic group C_2 = \{e, g \mid g^2 = e\}, the induced heap on its underlying set uses the ternary operation [a, b, c] = a b^{-1} c, resulting in a two-element heap where the operation distinguishes non-identity elements without specifying e.[29] More generally, affine spaces over vector spaces form heaps, with the ternary operation given by the affine combination [a, b, c] = a - b + c (interpreting the operations via the underlying vector space structure), capturing translations without a fixed origin.[30]
Theoretically, heaps generalize groups by omitting a specified identity, allowing flexible choice of unit while preserving algebraic coherence; this makes them valuable in the study of ternary operations and Mal'cev varieties, where the para-associative axiom aligns with Mal'cev conditions for permutability in varieties of algebras.[29] In Mal'cev varieties, heaps exemplify structures admitting ternary terms that permute coordinates, facilitating connections to loop theory and coordinate geometries.
To see how a group emerges from a heap, select a base element e \in H and define a binary operation x * z = [x, e, z]. This satisfies the group axioms: e acts as identity since [x, e, e] = x and [e, e, z] = z by biunitarity; associativity follows from para-associativity, as (x * y) * z = [[x, e, y], e, z] = [x, e, [y, e, z]] = x * (y * z); and inverses exist via x^{-1} * z = [z, x, e], ensuring solvability. Thus, every heap is a torsor over the group it generates.[29]
Other uses
Heap leaching
Heap leaching is a hydrometallurgical technique employed in the mining industry to extract valuable metals from low-grade ores, involving the stacking of crushed ore into large heaps and percolating it with chemical solutions called lixiviants to dissolve and recover the target metals.[31] This method is particularly suited for ores that are uneconomical to process through traditional milling due to their low metal content, typically below 1% for copper or 1 gram per ton for gold.[32]
The process begins with mining and crushing the ore to a size of 6-50 mm, often followed by agglomeration with cement or lime to improve permeability, before stacking it on impermeable liners or pads to form heaps typically 6-10 meters high per lift, with total heights reaching up to 60 meters in stacked configurations.[33] The heaps, which can cover areas of several hectares, are then irrigated with lixiviants such as dilute sulfuric acid (pH 1.5-2.0) for copper extraction or alkaline cyanide solutions (0.05-0.1% NaCN) for gold and silver, applied at rates of 5-10 liters per square meter per hour over periods ranging from 30-90 days.[34] The pregnant leach solution, containing dissolved metals, drains to collection ponds at the base, where it undergoes recovery processes like solvent extraction and electrowinning for copper or carbon adsorption and elution for gold, achieving recoveries of 50-90% for gold oxides[32] and 70-90% for copper oxides.[35] The barren solution is recycled to minimize reagent use.
Heap leaching finds primary applications in the extraction of gold, copper, uranium, and nickel from low-grade deposits, with gold recovery via cyanide leaching commonly applied to oxide ores yielding up to 90% efficiency, while copper uses acid leaching on oxide and secondary sulfide ores.[33] As of 2023, heap leaching accounts for approximately 20-25% of global copper production.[36] For gold, it processes ores as low as 0.5 g/t, contributing significantly to production from operations like Nevada's Cortez mine.[33] Uranium and nickel extractions, such as bioleaching with bacteria-assisted processes, are also viable for specific low-grade deposits.
The technique offers advantages including low capital and operating costs—typically under $10-20 per ton of ore compared to $30-50 per ton for milling—due to minimal grinding, lower energy consumption (often 50% less), and scalability for large volumes without extensive infrastructure.[37] It enables economic recovery from ores previously considered waste, with rapid payback periods of 2-3 years for viable projects.[31]
However, environmental concerns include the risk of lixiviant spills, such as cyanide toxicity leading to wildlife deaths and water contamination, as well as acid mine drainage generating low-pH effluents with heavy metals that can persist post-closure.[38] Heap operations produce large waste volumes—for instance, extracting 1 gram of gold may require processing over 20 tons of ore—necessitating extensive land use and reclamation, with regulations like the U.S. Clean Water Act mandating liners, monitoring, and neutralization to mitigate groundwater impacts.[39]
Historically, heap leaching evolved from ancient practices like 16th-century copper extraction in Hungary but saw modern development in the 1960s for copper in Chile and the U.S., expanding to gold in the 1970s with the pioneering Cortez operation in Nevada in 1969, which demonstrated commercial viability for low-grade gold ores.[34] By the 1980s, it had become a cornerstone of hydrometallurgy, with ongoing innovations in bioleaching and agglomeration enhancing efficiency.[33]
General meaning and etymology
A heap is defined as an untidy accumulation or pile of objects, often arranged in an irregular or haphazard manner, such as a heap of rubbish, sand, or discarded clothes.[40] In everyday language, the term commonly describes piles of earth, waste, or personal belongings, evoking a sense of disorder or abundance.[41] Metaphorically, it signifies a large or excessive quantity, as in "heaps of money" or "heaps of trouble," emphasizing profusion rather than structure.[42]
The word "heap" appears in idiomatic expressions rooted in historical and cultural contexts, such as the biblical phrase "heap coals of fire" from Proverbs 25:22, which metaphorically means to provoke remorse or shame through acts of kindness toward an enemy. This usage, echoed in Romans 12:20, illustrates the term's application to emotional or moral accumulation.
Etymologically, "heap" derives from Old English hēap, meaning "troop, multitude, or pile," from Proto-Germanic haupaz ("heap"), possibly from Proto-Indo-European koupos ("hill").[43][42] Cognates include Dutch hoop and German Haufen, both denoting crowds or piles.[43] The term has been in use since before the 12th century for physical accumulations, evolving by the 14th century to encompass abstract multitudes, a sense that later inspired the "heap" metaphor in computing for disorganized memory allocation.
In literature, "heap" often conveys wretchedness or excess, symbolizing chaos. Historically, it has influenced surnames like Heap, originating from Anglo-Saxon descriptors of hilly terrains or piles, and place names such as Heap Bridge in Bury, Lancashire, England, referring to a mound or elevated land.[44]