Binary heap
A binary heap is a specialized tree-based data structure that is a complete binary tree satisfying the heap property: in a min-heap, the key of each node is less than or equal to the keys of its children, while in a max-heap, it is greater than or equal to them.[1][2] This structure ensures that the root node always holds the minimum (or maximum) key, making it efficient for priority queue operations without requiring a fully sorted order among sibling nodes.[1][2]
Binary heaps maintain two fundamental properties: the shape property, where the tree is complete (all levels are fully filled except possibly the last, which is filled from left to right), and the heap ordering property as described above.[1][2] This allows heaps to be compactly represented in an array without explicit pointers, using level-order traversal: the root is at index 0 (or 1), with left and right children at indices 2i+1 and 2i+2 (or 2i and 2i+1 for 1-based indexing).[2] The height of the tree is O(log n) for n elements, which bounds the time complexity of key operations.[1][2]
Common operations on a binary heap include insertion, which adds a new element at the end of the array and "percolates" it up to restore the heap property in O(log n) time; extract-min (or extract-max), which removes and returns the root while replacing it with the last element and percolating down in O(log n) time; and heapify, which builds a heap from an unsorted array in O(n) time by starting from the bottom (non-leaf nodes) and sifting down to restore the heap property.[1][2] These operations enable efficient implementation of priority queues, where elements are dequeued based on priority rather than insertion order.[1][2]
Binary heaps are foundational in algorithms such as heapsort, which sorts an array in O(n log n) time by building a max-heap and repeatedly extracting the maximum, and they underpin many applications in operating systems (e.g., process scheduling), graph algorithms (e.g., Dijkstra's shortest path), and event-driven simulations requiring fast access to the highest-priority item.[1][2]
Introduction
Definition
A binary heap is a complete binary tree in which every node satisfies the heap property: in a min-heap, the value stored in each parent node is less than or equal to the values in its children; in a max-heap, the parent value is greater than or equal to the values in its children.[3]
A complete binary tree is defined such that all levels are fully filled except possibly the last, which is filled from left to right, leaving no gaps between nodes on that level.[4] This structure ensures the tree remains balanced and nearly full at all times.[3]
The binary heap data structure was introduced by J. W. J. Williams in 1964 as part of his algorithm for heapsort.[5] Visually, it takes the form of a tree with the root positioned at the top and child nodes arrayed below in successive levels, maintaining a compact layout with no interruptions in the filling of lower levels.[3]
Properties
A binary heap is a complete binary tree with n elements, resulting in a height of \lfloor \log_2 n \rfloor, which provides a balanced structure where all levels are fully filled except possibly the last, filled from left to right.[6] This balance distinguishes binary heaps from unbalanced trees, ensuring consistent depth across nodes.[7]
In a min-heap, the root node always contains the smallest element among all nodes, while in a max-heap, it contains the largest; this extremum location arises directly from the heap-order property, where each parent is smaller (min-heap) or larger (max-heap) than or equal to its children. Unlike binary search trees, binary heaps offer no guarantee of in-order traversal yielding sorted elements, as the ordering applies solely to the parent-child relationship without left-right distinctions.[8]
The heap-order property extends transitively: for any node, all its ancestors satisfy the ordering relative to it, meaning in a min-heap, every ancestor has a value less than or equal to the node's value, and vice versa for max-heaps; this follows inductively from the parent-child rule applied along the path from root to the node.[7]
This combination of properties ensures efficient priority queue behavior by positioning the extremum at the root for immediate access and leveraging the logarithmic height for adjustments that propagate along short paths to restore order after modifications, without requiring global rebalancing.
Representation
Array Storage
Binary heaps are typically implemented using a contiguous array to represent the underlying complete binary tree structure, enabling efficient storage without explicit pointers to child nodes. The nodes are mapped to array indices via level-order traversal, starting with the root at index 0, followed by its left child at index 1, right child at index 2, and subsequent nodes filling left to right across each level.[9] This representation leverages the complete binary tree property, where all levels are fully filled except possibly the last, which is filled from left to right.[5]
This array-based storage offers significant advantages in terms of space efficiency, as it requires no additional memory for pointers or null references to absent children, achieving O(1) auxiliary space beyond the n elements themselves.[5] Furthermore, the contiguous allocation improves cache performance by promoting spatial locality, where accessing parent and child nodes involves nearby memory addresses, reducing cache misses compared to pointer-based tree implementations.[10]
For example, consider a complete binary tree with 7 nodes: the array would store the root at index 0, its left child at 1, right child at 2, the left subtree's children at 3 and 4, and the right subtree's children at 5 and 6, as [root, left, right, left-left, left-right, right-left, right-right].[9]
When the last level is incomplete, the array size is exactly equal to the number of nodes present, avoiding any wasted space for missing children on the right side of the last level.[5] Basic access to determine if a node at index i has children can be checked using array bounds, ensuring operations stay within the valid range without needing explicit null checks.
The following pseudocode illustrates simple checks for left and right children in a 0-based array of size n:
function hasLeftChild(i, n):
return 2 * i + 1 < n
function hasRightChild(i, n):
return 2 * i + 2 < n
function hasLeftChild(i, n):
return 2 * i + 1 < n
function hasRightChild(i, n):
return 2 * i + 2 < n
These checks rely solely on index arithmetic and the array length, maintaining the efficiency of the representation.[9]
Index Calculations
Binary heaps can use either 0-based or 1-based array indexing, with 1-based being common in some implementations to simplify parent calculations.
0-Based Indexing
In the array-based representation of a binary heap with 0-based indexing, navigation between parent and child nodes relies on mathematical formulas that exploit the level-order (breadth-first) arrangement of the complete binary tree. For a node at index i in an array of size n, the left child is located at index $2i + 1 and the right child at $2i + 2, assuming these indices are less than n.[11] The parent of a node at index i > 0 is at index \lfloor (i - 1)/2 \rfloor, while the root node at index 0 has no parent.[11]
These formulas arise from the systematic numbering of nodes in level order, where each level of the tree is filled from left to right before proceeding to the next. Starting with the root at index 0, the first level occupies indices 1 and 2, the second level indices 3 through 6, and so on, with each subsequent level containing twice as many nodes as the previous. To reach a child's position from the parent at i, the index is effectively doubled to shift to the doubled capacity of the next level; the additions of 1 and 2 then position the left child immediately after the parent's "influence" in the numbering and the right child as its successor. Conversely, the parent formula reverses this by subtracting 1 to align with the prior level's end and dividing by 2 (with flooring) to return to the parent's slot.[11][12]
1-Based Indexing
In 1-based indexing, the root is at index 1, the left child of node i is at $2i, the right child at $2i + 1, and the parent of node i > 1 is at \lfloor i / 2 \rfloor. This avoids the offset in parent calculation and is often preferred in theoretical contexts or languages where arrays start at 1 (e.g., some pseudocode). The formulas derive similarly from level-order numbering starting at 1, doubling indices for children, and halving for parents.[13][9]
Edge cases must be handled to respect the complete tree's shape. The root has no parent, so the parent formula applies only for i > 0 (0-based) or i > 1 (1-based). For children, existence is verified against array bounds: if $2i + 1 \geq n (0-based) or $2i > n (1-based), no left child exists, implying no right child either (since the tree is complete and filled left-to-right). These checks prevent invalid access in partially filled heaps.[11]
The correctness of these formulas stems from the bijection between array indices and level-order positions in a complete binary tree, ensuring that parent-child links align precisely without gaps or overlaps. This mapping preserves the tree's structural integrity because the consecutive numbering guarantees that a parent's children occupy the two indices immediately following the subtree rooted at the parent in the breadth-first sequence, maintaining the binary branching and completeness properties inherent to the heap. The choice between 0- and 1-based indexing is largely conventional, with both supporting O(1) navigation.[11]
Construction
Building a Heap
The construction of a binary heap from an unsorted array involves transforming the array, which represents a complete binary tree, into a structure that satisfies the heap property. This process, known as building a heap, was originally described by J. W. J. Williams as part of the heapsort algorithm, where the array is initialized as a near-complete tree and the heap order is enforced progressively.[5]
The overall algorithm proceeds bottom-up: the array is treated as a complete binary tree with n elements, indexed from 0 to n-1. The last non-leaf node is located at index floor(n/2) - 1, using standard index calculations for parent-child relationships in array-based heaps. Starting from this index and iterating downward to the root (index 0), the heapify procedure is applied to each subtree rooted at index i. This ensures that when heapify is invoked on a node, its subtrees already satisfy the heap property, progressively building the full heap from the leaves upward.[14]
This bottom-up approach is efficient because it minimizes unnecessary operations in the upper levels of the tree; by heapifying smaller subtrees first, the algorithm avoids propagating changes through the entire height of the tree for every element, unlike successive insertions that would require bubbling each new element from leaf to root.[14]
Consider the example of building a max-heap from the unsorted array A = [4, 1, 3, 2, 16, 9, 10], with n=7 (indices 0 to 6). The last non-leaf node is at index floor(7/2) - 1 = 2. The initial array representation is:
Index: 0 1 2 3 4 5 6
Value: 4 1 3 2 16 9 10
Index: 0 1 2 3 4 5 6
Value: 4 1 3 2 16 9 10
- Apply heapify at index 2 (value 3, children at 5 and 6: 9 and 10). Since 3 < 10, swap with 10; the subtree now satisfies the max-heap property. Array: [4, 1, 10, 2, 16, 9, 3].
- Apply heapify at index 1 (value 1, children at 3 and 4: 2 and 16). Since 1 < 16, swap with 16; then at the new position (index 4, value 1, no children), done. Array: [4, 16, 10, 2, 1, 9, 3].
- Apply heapify at index 0 (value 4, children at 1 and 2: 16 and 10). Since 4 < 16, swap with 16; then at index 1 (value 4, children at 3 and 4: 2 and 1), 4 > 2 and 4 > 1, done. Final array: [16, 4, 10, 2, 1, 9, 3].
This results in a max-heap where the parent is greater than or equal to its children. The corresponding tree structure after construction is a complete binary tree with root 16, left subtree rooted at 4 (with leaves 2 and 1), and right subtree rooted at 10 (with leaves 9 and 3).[15]
In the context of priority queues, binary heaps provide an efficient implementation, and the building process allows for rapid initialization from an initial set of elements, enabling subsequent operations like insertion and extraction in O(log n) time.[5]
Heapify Procedure
The heapify procedure restores the binary heap property when it is violated at a specific node, under the invariant that the subtrees rooted at its children are already valid heaps, with the violation localized to the node itself.[5] This operation, central to maintaining heap integrity, was introduced as part of the heapsort algorithm to efficiently adjust the structure after modifications.[16] There are two primary forms: heapify-down, which propagates a violation downward, and heapify-up, which propagates it upward.
In a min-heap, the heapify-down (also known as sift-down) operation begins at a given index i representing the node with the violation. It identifies the smallest among the node and its children; if a child is smaller, it swaps the node with that child and recurses on the child's position until no violation exists.[16] For a max-heap, the process is analogous but selects the largest child and swaps if the parent is smaller. The child indices are calculated as left = 2i and right = 2i + 1 in 1-based array indexing.[16]
The following pseudocode illustrates the min-heapify-down procedure, assuming a 1-based array A and a heap size denoted by heap_size[A]:
MIN-HEAPIFY(A, i)
smallest = i
l = 2 * i
r = 2 * i + 1
if l ≤ heap_size[A] and A[l] < A[smallest]
smallest = l
if r ≤ heap_size[A] and A[r] < A[smallest]
smallest = r
if smallest ≠ i
exchange A[i] with A[smallest]
MIN-HEAPIFY(A, smallest)
MIN-HEAPIFY(A, i)
smallest = i
l = 2 * i
r = 2 * i + 1
if l ≤ heap_size[A] and A[l] < A[smallest]
smallest = l
if r ≤ heap_size[A] and A[r] < A[smallest]
smallest = r
if smallest ≠ i
exchange A[i] with A[smallest]
MIN-HEAPIFY(A, smallest)
[16]
The heapify-up (also known as sift-up or bubble-up) operation, used after inserting a new element at the end of the heap, starts from that leaf position and compares the node with its parent. If the node violates the property (smaller than parent in a min-heap), it swaps with the parent and recurses upward until the property holds or the root is reached.[16] For a min-heap, the pseudocode is:
MIN-HEAPIFY-UP(A, i)
while i > 1 and A[i] < A[PARENT(i)]
exchange A[i] with A[PARENT(i)]
i = PARENT(i)
MIN-HEAPIFY-UP(A, i)
while i > 1 and A[i] < A[PARENT(i)]
exchange A[i] with A[PARENT(i)]
i = PARENT(i)
where PARENT(i) = ⌊i/2⌋.[16]
Heapify-down is employed during minimum extraction (to restore the heap after root removal) and in the bottom-up construction of a heap from an array, while heapify-up is applied following insertions or decrease-key operations to maintain the ordering.[16]
To illustrate heapify-down in a min-heap, consider an array A = [4, 1, 3, 2] (1-based indices: position 1=4, 2=1, 3=3, 4=2), where the subtrees are valid min-heaps but the root violates the property (4 > children 1 and 3). The smallest child is at index 2 (value 1), so swap positions 1 and 2, yielding A = [1, 4, 3, 2]. Now at index 2 (value 4), the only child is at index 4 (value 2 < 4), so swap them, resulting in A = [1, 2, 3, 4]. No further children exist, so the heap property is restored. This process fixes the single violation through successive downward swaps.[16]
Operations
Insertion
Insertion into a binary heap involves adding a new element while preserving the complete binary tree structure and the heap property. The process begins by appending the new element to the end of the underlying array, which corresponds to the next available position in the last level of the tree, maintaining the completeness. This initial placement ensures the tree remains complete before adjusting for the heap order.
To restore the heap property, a heapify-up (or sift-up) operation is performed starting from the new element's position. In a min-heap, the new element is compared with its parent; if it is smaller than the parent, they are swapped, and the comparison continues with the new parent until the element reaches a position where it is not smaller than its parent or the root is reached. This bubbling up corrects any violations introduced by the insertion. For a max-heap, the comparison reverses, swapping if the new element is larger than its parent. The parent index is calculated as floor(i/2) for a 1-based array indexing.[1]
The following pseudocode illustrates the insertion for a min-heap using 1-based indexing, where the array is A[1..n] and n is the current heap size:
procedure MIN-HEAP-INSERT(A, key)
n = A.heap-size
A.heap-size = n + 1
i = n + 1
A[i] = key
while i > 1 and A[i] < A[floor(i/2)]
swap A[i] and A[floor(i/2)]
i = floor(i/2)
procedure MIN-HEAP-INSERT(A, key)
n = A.heap-size
A.heap-size = n + 1
i = n + 1
A[i] = key
while i > 1 and A[i] < A[floor(i/2)]
swap A[i] and A[floor(i/2)]
i = floor(i/2)
This procedure directly inserts the key and bubbles it up as needed. An equivalent approach, as described in standard implementations, temporarily places a minimal value (e.g., negative infinity for max-heaps) at the new position and then uses an increase-key operation to set the value and adjust upward.[1]
Consider inserting the value 5 into a min-heap represented by the array [1, 3, 2, 4] (1-based: A[17]=1, A[18]=3, A[19]=2, A[20]=4), which forms the tree:
1
/ \
3 2
/
4
1
/ \
3 2
/
4
Append 5 at position 5: [1, 3, 2, 4, 5]. The parent of position 5 is position 2 (value 3). Since 5 > 3, no swap is needed, and the heap property holds. The resulting array is [1, 3, 2, 4, 5], with the tree:
1
/ \
3 2
/ \
4 5
1
/ \
3 2
/ \
4 5
[1]
The insertion operation requires additional space proportional to the height of the tree in recursive implementations, though iterative versions use amortized O(1) extra space per insertion beyond the array growth.
The extraction operation in a binary heap removes and returns the root element, which holds the minimum (in a min-heap) or maximum (in a max-heap) value according to the heap property.[21] This is a fundamental operation for priority queues implemented via heaps, enabling efficient access to the extremal element.[6]
To perform extraction, the procedure first saves the root value in a temporary variable. The last element in the heap array is then moved to the root position to maintain the complete binary tree structure, as removing the root directly would otherwise disrupt the shape. The heap size is decremented by one, effectively removing the original last element. Finally, a heapify-down (or sift-down) operation is applied starting from the root to restore the heap property by bubbling the new root down the path of smallest (for min-heap) or largest (for max-heap) children until the invariant holds.[21] In a min-heap, this sift-down compares the current node with its children and swaps with the smallest child if the heap property is violated, continuing recursively or iteratively down the tree.[22]
The following pseudocode illustrates the extract-min procedure for a min-heap represented in a 0-indexed array A of size n, assuming the heapify-down function (also known as MIN-HEAPIFY) is available from the heapify procedure:
MIN-HEAP-EXTRACT-MIN(A, n)
if n < 1
error "Heap underflow"
min = A[0]
A[0] = A[n-1]
n = n - 1
MIN-HEAPIFY(A, 0, n)
return min
MIN-HEAP-EXTRACT-MIN(A, n)
if n < 1
error "Heap underflow"
min = A[0]
A[0] = A[n-1]
n = n - 1
MIN-HEAPIFY(A, 0, n)
return min
[22][23]
For example, consider a min-heap stored in a 1-indexed array [1, 2, 3, 4, 5] (with root at index 1), forming the tree:
1
/ \
2 3
/ \
4 5
1
/ \
2 3
/ \
4 5
Extracting the minimum (1) involves saving 1, moving 5 to the root, reducing size to 4, and heapifying down: 5 swaps with 2 (the smaller child), then the new position of 5 (now at index 2) swaps with 4 (its only child), resulting in [2, 4, 3, 5]. The tree now is:
2
/ \
4 3
\
5
2
/ \
4 3
\
5
This restores the min-heap property.[21]
If the heap is empty (size 0), the extraction operation typically returns a null value or raises an underflow error to indicate no element is available.[22]
Decrease-Key
The decrease-key operation in a binary min-heap updates the value of an element at a known index to a smaller value and restores the min-heap property by bubbling the element upward if necessary. This operation is essential in algorithms like Dijkstra's shortest-path algorithm, where vertex distances may require multiple updates during execution, enabling efficient priority adjustments in the heap-based priority queue.[24]
The operation assumes the index i of the target node is provided in advance, typically through handles or direct array access in priority queue implementations, as locating the element otherwise would require a linear-time search.[25] For a min-heap, after assigning the new smaller value to the array element at index i, the procedure checks if it violates the heap property with its parent; if the new value is smaller than the parent's value, it repeatedly swaps the element with its parent until the property holds or the root is reached.[26] This bubbling-up process, akin to the heapify-up procedure, ensures the structure remains a valid min-heap.[27]
The following pseudocode illustrates the decrease-key operation for a min-heap stored in an array A, where \text{PARENT}(i) = \lfloor i/2 \rfloor for i > 0:
HEAP-DECREASE-KEY(A, i, key)
1 A[i] ← key
2 while i > 1 and A[PARENT(i)] > A[i]
3 swap A[i] ↔ A[PARENT(i)]
4 i ← PARENT(i)
HEAP-DECREASE-KEY(A, i, key)
1 A[i] ← key
2 while i > 1 and A[PARENT(i)] > A[i]
3 swap A[i] ↔ A[PARENT(i)]
4 i ← PARENT(i)
This runs in O(\log n) time, where n is the heap size, as the swaps traverse at most the tree height.[25][26]
Consider a min-heap array [3, 5, 4, 7] (indices starting at 0). Decreasing the key at index 0 from 3 to 1 yields [1, 5, 4, 7]; no swaps are needed since 1 remains smaller than its children 5 and 4. Now, decreasing the key at index 1 from 5 to 0 yields [1, 0, 4, 7]; this violates the property with parent 1, so swap positions 0 and 1 to get [0, 1, 4, 7], after which the root is reached and the heap property holds (0 ≤ 1, 0 ≤ 4, 1 ≤ 7).[25]
Increase-Key
In a binary min-heap, the increase-key operation updates the value of a node at a known index i to a larger value k (where k \geq the current value), which may violate the min-heap property if the new value exceeds the smallest among its children. To restore the property, the procedure first assigns the new value to the array position and then performs a sift-down operation starting from index i, swapping the node with its smallest child if necessary until the subtree rooted at i satisfies the min-heap invariant. This contrasts with the decrease-key operation, which propagates upward, highlighting the asymmetry of key updates in heaps.[28]
The steps are as follows:
- Assign A = k.
- If node i has at least one child and A is greater than the minimum child value, swap A with the smallest child's value.
- Repeat the comparison and swap from the child's index until no violation occurs or a leaf is reached.
This relies on the heapify-down (or sift-down) procedure to maintain the structure, ensuring the overall heap property holds after the update.
Here is pseudocode for the operation (assuming a 1-based array indexing and the heapify-down procedure as defined earlier):
INCREASE-KEY(A, i, k)
if k < A[i]
error "new key is smaller"
A[i] = k
HEAPIFY-DOWN(A, i)
INCREASE-KEY(A, i, k)
if k < A[i]
error "new key is smaller"
A[i] = k
HEAPIFY-DOWN(A, i)
The time complexity is O(\log n) in the worst case, matching the height of the heap.
For example, consider a min-heap array A = [1, 3, 2, 7, 5, 4] (1-based indices: positions 1 to 6). The tree structure has root 1, left subtree under 3 (with children 7 and 5), and right subtree under 2 (with child 4). Now increase the key at index 2 from 3 to 6. After assignment, A{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}} = 6, which violates the property with its children (min child is 5 at index 5). Swap positions 2 and 5: A = [1, 5, 2, 7, 6, 4]. At new position 5 (value 6), there are no children, so the process stops. The resulting array [1, 5, 2, 7, 6, 4] maintains the min-heap property.
The increase-key operation is less frequently used than decrease-key in min-heap-based priority queues, as many applications (e.g., shortest-path algorithms) involve reducing priorities rather than increasing them. However, it finds utility in update scenarios within max-heap contexts or when priorities may rise, such as dynamic scheduling systems.[28]
Search
Searching for an arbitrary element in a binary heap, or determining whether it exists, requires a linear scan through the entire array representation, resulting in O(n) time complexity in the worst case, where n is the number of elements.[29] This inefficiency arises because the heap property enforces a partial order—parent nodes are smaller (in a min-heap) or larger (in a max-heap) than their children—but does not maintain a global sorted order that would enable faster traversal, unlike structures such as binary search trees.[9] Binary heaps are typically implemented using contiguous array storage, which allows straightforward iteration for the scan but offers no indexing advantage for arbitrary lookups.[29]
Accessing the minimum or maximum element is an exception, achievable in O(1) time by directly examining the root of the heap.[9] For any other target value, however, the position is unpredictable due to the lack of sorted traversal paths, necessitating a full examination of all elements to confirm presence or absence.[29]
The standard implementation of this search uses a simple loop over the array:
function search(heap, target):
for i from 0 to heap.size - 1:
if heap[i] == target:
return i // index of the element, or true if checking existence
return -1 // not found, or false
function search(heap, target):
for i from 0 to heap.size - 1:
if heap[i] == target:
return i // index of the element, or true if checking existence
return -1 // not found, or false
This pseudocode directly translates to O(n) runtime, as each iteration performs a constant-time comparison, and up to n comparisons may be needed.[29]
Binary heaps are designed primarily as efficient priority queues, optimizing operations like insertion and minimum/maximum extraction to O(log n) time while deprioritizing search to favor these core functionalities.[9] The O(n) search cost reflects this trade-off, as maintaining additional ordering for logarithmic searches would complicate the structure and increase overhead for heap-specific tasks.[29] When applications demand frequent arbitrary searches alongside priority operations, hybrid approaches or separate data structures—such as combining a heap with a hash table for indexing—are recommended to mitigate the linear-time bottleneck.[9]
For illustration, consider searching for the value 4 in a min-heap array [1, 3, 2, 5, 4], where indices start at 0. The scan checks 1 (no match), 3 (no), 2 (no), 5 (no), and finally 4 (match at index 4), requiring examination of all five elements despite the early positions being irrelevant.[29]
Arbitrary Deletion
Arbitrary deletion in a binary heap refers to the removal of a specific element that is not necessarily the root, requiring first locating its position within the heap structure. To perform this operation, the index i of the target element must be identified, typically through a linear scan of the heap array, which takes O(n) time in the worst case where n is the number of elements.[30]
Once the index i is found, if i = 0 (the root), the deletion proceeds as in standard extraction by replacing it with the last element and heapifying down. For a non-root element, the procedure involves replacing the element at index i with the last element in the heap (at index n-1), reducing the heap size by one (n \leftarrow n-1), and then restoring the heap property starting from position i. This restoration requires checking whether the new element at i violates the heap order with its parent (potentially requiring heapify-up) or with its children (potentially requiring heapify-down). In the worst case, both directions may need adjustment, though typically only one is necessary depending on the relative value of the replacement element compared to the original.[30][31]
The following pseudocode outlines the process for a min-heap, assuming the index i is known:
function arbitraryDelete(i):
if i == 0:
return extractMin() // Standard root extraction
else:
heap[i] = heap[n-1]
n = n - 1
if heap[i] < heap[parent(i)]: // Violates with parent
heapifyUp(i)
else:
heapifyDown(i)
function arbitraryDelete(i):
if i == 0:
return extractMin() // Standard root extraction
else:
heap[i] = heap[n-1]
n = n - 1
if heap[i] < heap[parent(i)]: // Violates with parent
heapifyUp(i)
else:
heapifyDown(i)
This approach leverages the existing heapify procedures to maintain the heap-ordered property efficiently after replacement.[30][31]
The primary challenge in arbitrary deletion arises from the O(n) cost of locating the element, combined with the O(\log n) time for the subsequent heapify operations, making the overall process inefficient for frequent use without additional indexing. In practice, arbitrary deletion is rare in binary heaps because it requires knowing the element's index (or "handle"); to avoid the search overhead, applications often maintain external handles to elements or opt for more advanced heap variants like Fibonacci heaps that support efficient arbitrary deletion.[30][31]
For example, consider a min-heap represented as the array [1, 3, 2, 5] with indices 0 to 3. To delete the element 3 at index 1, first move the last element 5 to index 1, reducing the size to 3, resulting in [1, 5, 2]. Since 5 > 1 (the parent), no heapify-up is needed, but 5 violates the min-heap property with its child 2, so heapify-down swaps 5 and 2, yielding [1, 2, 5], which satisfies the heap order.[30]
Variants
Min-Heap and Max-Heap
A binary min-heap is a complete binary tree in which each node satisfies the min-heap property: the value of every parent node is less than or equal to the values of its children, ensuring that the minimum element resides at the root.[21] This structure is particularly useful for implementing priority queues where the smallest-priority item must be extracted first, such as in scheduling algorithms or Dijkstra's shortest-path algorithm.[32]
In contrast, a binary max-heap adheres to the max-heap property, where the value of every parent node is greater than or equal to the values of its children, placing the maximum element at the root.[21] Max-heaps are commonly employed in applications requiring the largest element to be prioritized, such as in the descending order phase of heapsort or certain selection algorithms.[32]
Both min-heaps and max-heaps share the same underlying complete binary tree structure and support identical operations with equivalent time complexities, differing only in the ordering invariant.[33] The choice between them depends on the specific application needs, such as whether minimum or maximum extraction is required.
One approach to simulate a max-heap using a min-heap implementation involves negating all key values before insertion and negating the result upon extraction; however, this method is inefficient for non-numeric keys or when negation alters semantics.[34]
For illustration, consider the array representation of a small heap with elements {1, 2, 3, 4}:
-
Min-heap array:
[1, 2, 3, 4]
1
/ \
2 3
/
4
1
/ \
2 3
/
4
Here, the root 1 is the minimum, and parents are ≤ children.[33]
-
Max-heap array:
[4, 3, 2, 1] (same shape, reversed ordering)
4
/ \
3 2
/
1
4
/ \
3 2
/
1
The root 4 is the maximum, with parents ≥ children.[32]
These side-by-side examples highlight the ordering differences while preserving the structural completeness of the binary tree.[21]
The binary heap, introduced in 1964 as part of the heapsort algorithm, serves as the foundational structure for several advanced priority queue implementations that address its limitations in operations like merging and decrease-key. Subsequent developments built upon this base, leading to more sophisticated heaps designed for specific algorithmic needs, such as efficient unions in graph processing.[35]
Binomial heaps, proposed in 1978, extend the binary heap concept by organizing elements into a forest of binomial trees, each of order corresponding to powers of two, enabling a union operation in O(log n) time that is particularly useful for mergeable priority queues.[35] This structure supports the same O(log n) worst-case bounds for insert, extract-min, and decrease-key as binary heaps but excels in scenarios requiring frequent merges, such as certain dynamic graph algorithms.[3]
Fibonacci heaps, developed in 1984 and formalized in 1987, further improve upon binomial heaps by allowing amortized O(1) time for decrease-key operations through a lazy implementation of linking trees with degree bounds, making them ideal for graph algorithms like Dijkstra's where decrease-key is frequent.[36] However, their practical performance suffers from higher constant factors compared to binary heaps due to complex pointer manipulations and potential for larger memory usage.[37]
Pairing heaps, introduced in 1986, offer a simpler alternative to Fibonacci heaps by using a self-adjusting tree structure that pairs subtrees during merges, achieving practical efficiency in many applications while being easier to implement than Fibonacci heaps.[38] Experimental evaluations show pairing heaps often outperform Fibonacci heaps in real-world scenarios due to reduced overhead, though their worst-case bounds remain partially unresolved.[38]
In comparison to balanced binary search trees (BSTs), which support O(log n) time for insert, delete, and search operations, binary heaps provide faster O(log n) insert and extract-min but degrade to O(n) for search, making heaps preferable for priority queue tasks where minimum extraction dominates over lookups.[39] Balanced BSTs, like AVL or red-black trees, are better suited when search efficiency is critical, as heaps do not maintain sorted order.[9]
Binary heaps are typically chosen for their simplicity and low constant factors in basic priority queue applications, while binomial and Fibonacci heaps are favored for algorithms needing efficient unions or decrease-keys, such as network optimization, and pairing heaps for a balance of performance and ease in practical implementations.[37]
Operation Runtimes
The time complexities of standard operations on a binary heap are determined by the structure's height, which is O(\log n) for n elements, and the need for linear scans in certain cases. Insertion involves adding an element at the end of the array representation and percolating it up to restore the heap property, taking O(\log n) time in the worst case. Extraction of the minimum (or maximum) element requires removing the root, replacing it with the last element, and percolating down, also O(\log n) in the worst case. The decrease-key operation, which reduces a node's key and percolates it up, requires O(\log n) time in the worst case, as does the symmetric increase-key operation, which percolates down. Searching for an arbitrary element necessitates a linear scan through the heap, resulting in O(n) time complexity. Arbitrary deletion combines searching for the element (O(n)) with removal and heap restoration (O(\log n)), yielding an overall worst-case time of O(n).
These bounds hold for both average and worst-case scenarios in most operations due to the balanced nature of the complete binary tree underlying the heap, though search and arbitrary deletion are dominated by the linear component regardless of input distribution.
| Operation | Average | Worst-case | Notes |
|---|
| Insertion | O(\log n) | O(\log n) | Traverses up to height; amortized same as worst. [1] |
| Extraction | O(\log n) | O(\log n) | Heapify-down from root; find-min/max is O(1). [1] |
| Decrease-key | O(\log n) | O(\log n) | Assumes known position; percolates up. [40] |
| Increase-key | O(\log n) | O(\log n) | Assumes known position; percolates down. [40] |
| Search | O(n) | O(n) | Linear scan; no ordering for faster lookup. [41] |
| Arbitrary deletion | O(n) | O(n) | O(n) search + O(\log n) removal/fix. [1] [41] |
Building Complexity
The construction of a binary heap from an unsorted array of n elements, known as the build-heap operation, achieves an overall time complexity of O(n). This efficiency arises from Floyd's bottom-up heapification algorithm, which starts by treating the array as a complete binary tree and then restores the heap property by calling the heapify procedure on each non-leaf node, beginning from the last non-leaf node and proceeding towards the root.
A naive approach of performing n successive insertions into an initially empty heap would require O(n \log n) time, as each insertion takes O(\log n) in the worst case; in contrast, the bottom-up method leverages the fact that most elements are already near their final positions in the complete binary tree representation, leading to significantly less sifting on average.
To prove the O(n) bound, consider the total cost of heapify operations across all nodes, where the cost for a node is proportional to its height h in the subtree rooted at that node (the maximum number of swaps needed). In a complete binary tree of n nodes, the number of nodes with height h is at most \lceil n / 2^{h+1} \rceil for h = 0, 1, \dots, \lfloor \log_2 n \rfloor. The total cost is thus bounded by
\sum_{h=0}^{\lfloor \log_2 n \rfloor} h \cdot \frac{n}{2^{h+1}} = O(n) \sum_{h=0}^{\infty} \frac{h}{2^{h+1}},
since the infinite series \sum_{h=0}^{\infty} h / 2^h = 2 converges to a constant. This summation shows that the costs "telescope" to linear time, with leaves (height 0) contributing O(n) at negligible cost per node, and higher levels having exponentially fewer nodes despite their O(\log n) cost.
An alternative perspective on the total time T(n) is T(n) = \sum_{i=1}^n O(\log (n - i + 1)), which approximates to O(n) through integral bounds or the above height-based analysis. In practice, for large n, the build-heap operation exhibits strictly linear performance, often using fewer than $2n comparisons, confirming its efficiency over the quadratic worst-case alternatives in older heap construction methods.