What a Binary Heap Is
A Binary Heap is a nearly complete binary tree that satisfies a specific ordering property, and it is typically stored implicitly in an array rather than using explicit pointer-based tree nodes. There are two variants: a Max-Heap, where every parent node's value is greater than or equal to its children's values, and a Min-Heap, where the opposite holds. This article focuses on max-heaps, since they are the basis for heapsort, though every operation has a direct min-heap analog.
Representing a Heap in an Array
Because a heap is a nearly complete binary tree, it can be stored compactly in a simple array, with the tree structure derived entirely from array indices rather than explicit pointers.
For a node at index i (using 1-based indexing):
PARENT(i) = ⌊i / 2⌋
LEFT(i) = 2i
RIGHT(i) = 2i + 1
Example heap: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
Index: 1 2 3 4 5 6 7 8 9 10
This represents the tree:
16
/ \
14 10
/ \ / \
8 7 9 3
/ \ |
2 4 1The Max-Heap Property requires that for every node i other than the root, A[PARENT(i)] ≥ A[i]. Note that this property only constrains parent-child relationships; it says nothing about the relative order of siblings or nodes in different subtrees, which is why a heap is not a fully sorted structure.
The Core Operation: MAX-HEAPIFY
MAX-HEAPIFY is the fundamental operation that maintains the max-heap property. It assumes the binary trees rooted at a node's left and right children are already valid max-heaps, but the node itself might violate the property by being smaller than one of its children. It fixes this by "sifting down" the violating value.
MAX-HEAPIFY(A, i, n):
l = LEFT(i)
r = RIGHT(i)
if l ≤ n and A[l] > A[i]:
largest = l
else:
largest = i
if r ≤ n and A[r] > A[largest]:
largest = r
if largest ≠ i:
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest, n)This algorithm compares the node against both its children, identifies the largest of the three, and if a child is larger than the node, swaps them and recursively continues fixing the heap property further down the tree. Since a heap has height Θ(log n), and MAX-HEAPIFY does constant work at each level as it descends, its running time is O(log n).
Building a Heap from an Unordered Array
Given an arbitrary array, BUILD-MAX-HEAP converts it into a valid max-heap by calling MAX-HEAPIFY on every non-leaf node, working from the last non-leaf node up to the root.
BUILD-MAX-HEAP(A, n):
for i = ⌊n/2⌋ downto 1:
MAX-HEAPIFY(A, i, n)The reason this starts at ⌊n/2⌋ rather than at the first element is that all array indices greater than ⌊n/2⌋ are leaves, which are trivially valid one-node heaps requiring no work.
A Surprising Result: BUILD-MAX-HEAP Runs in Linear Time
A naive analysis might suggest that since there are roughly n/2 calls to MAX-HEAPIFY, each costing O(log n), the total cost is O(n log n). This bound is correct but not tight. A more careful analysis reveals that most nodes are near the bottom of the tree, where MAX-HEAPIFY does very little work, since most subtrees are short.
At height h, there are at most ⌈n/2^(h+1)⌉ nodes,
and MAX-HEAPIFY on a node of height h costs O(h)
Total cost = Σ (h=0 to ⌊log n⌋) ⌈n/2^(h+1)⌉ · O(h)
= O(n · Σ (h=0 to ∞) h/2^h)
Using the known result Σ (h=0 to ∞) h·xʰ = x/(1-x)²
with x = 1/2, this sum evaluates to a constant
Therefore, Total cost = O(n)This proves that BUILD-MAX-HEAP runs in Θ(n) time, a linear-time algorithm — significantly better than the loose O(n log n) bound a naive analysis would suggest. This is a classic example of why careful, precise analysis matters far more than a quick, loose estimate.
The Complete Heapsort Algorithm
Heapsort combines the heap-building procedure with a repeated extraction process to sort an array in place.
HEAPSORT(A, n):
BUILD-MAX-HEAP(A, n)
for i = n downto 2:
exchange A[1] with A[i]
n = n - 1 (shrink the heap, excluding the sorted suffix)
MAX-HEAPIFY(A, 1, n)The algorithm works by repeatedly extracting the maximum element (always at the root, index 1) and placing it at the end of the currently unsorted region, then restoring the heap property on the now-smaller heap. Each of these n-1 extraction steps costs O(log n) for the MAX-HEAPIFY call, giving a total running time of Θ(n log n) for the sorting phase, plus the Θ(n) for the initial build, for an overall running time of Θ(n log n).
Heapsort has an important practical advantage over merge sort, another Θ(n log n) algorithm covered later in this series: it sorts In Place, requiring only a constant amount of memory beyond the input array itself, whereas merge sort requires Θ(n) additional memory.
Priority Queues: The Practical Application of Heaps
Beyond sorting, the heap's real-world importance comes from its use as the underlying data structure for a Priority Queue, an abstract data type that maintains a set of elements, each with an associated priority, and supports efficiently retrieving and removing the highest-priority element.
Core priority queue operations, using a max-heap:
MAX-HEAP-MAXIMUM(A): return A[1] — O(1)
MAX-HEAP-EXTRACT-MAX(A, n): remove and return the max — O(log n)
MAX-HEAP-INCREASE-KEY(A, i, key): raise a key's value — O(log n)
MAX-HEAP-INSERT(A, key, n): add a new element — O(log n)MAX-HEAP-EXTRACT-MAX removes the root, moves the last element to the root position, shrinks the heap size, and calls MAX-HEAPIFY to restore the property. MAX-HEAP-INCREASE-KEY raises an element's priority and then "bubbles it up" toward the root by repeatedly swapping with its parent until the heap property is restored. MAX-HEAP-INSERT adds a new element at the bottom of the heap with a minimal initial value, then calls increase-key to raise it to its actual priority and bubble it into position.
Why Priority Queues Matter Throughout Algorithm Design
Priority queues built on heaps are a fundamental building block used throughout the rest of this series, most notably in Dijkstra's algorithm for shortest paths and Prim's algorithm for minimum spanning trees, both covered later in this series, where efficiently selecting the "next best" element at each step is central to the algorithm's correctness and efficiency. The O(log n) cost of heap operations, rather than the O(n) cost of a naive linear scan through an unsorted list, is often what makes these graph algorithms practical for large inputs.