Of all the subroutines involved in Heap Sort, I think heapify (also called sift-down) is the one that deserves the most careful, standalone attention, because it’s the single repair operation that every other part of the algorithm depends on. Both the build-heap phase and the extraction phase I cover in my other two Heap Sort articles are really just different contexts for calling this one procedure. This article is my deep dive into exactly how heapify restores the max-heap property at a single node, and why I can trust it to always work correctly.
History and Background
The heapify procedure was introduced as part of J.W.J. Williams’ original 1964 paper on Heapsort in Communications of the ACM, alongside the binary heap data structure itself. While Williams’ original presentation and Robert Floyd’s subsequent refinement focused on the overall sorting algorithm and its efficient construction, the underlying repair operation — moving a node downward through the tree until the heap property is restored — is the atomic unit both of their contributions are built from.
This operation has remained essentially unchanged since 1964, and it appears, sometimes under different names (sift-down, trickle-down, percolate-down), across virtually every textbook and implementation of binary heaps I’ve come across, which is a testament to how well the original design has held up.
Problem Statement
The problem I’m solving here is narrow and specific: given a binary heap where exactly one node may violate the max-heap property (meaning it might be smaller than one or both of its children), while every other node in the tree already satisfies the property, restore the max-heap property for the entire structure — using the fewest comparisons and swaps possible.
This is a much more constrained problem than building a heap from scratch, and that constraint is exactly what makes heapify efficient: I only need to fix a single “broken” spot, not rebuild everything.
Core Concepts
- Single-point violation: The assumption that only one node (typically the one just modified, such as the root after an extraction) might violate the heap property, while its child subtrees are already valid heaps.
- Largest-of-three comparison: At each step,
heapifycompares the current node against both of its children (when they exist) to determine which of the three holds the largest value. - Sift-down (trickle-down): The motion of an out-of-place element moving downward through the tree, one level at a time, until it reaches a position where it’s no longer smaller than either child.
- Recursive subtree repair: After a swap, the violation may now exist one level deeper (at the position the element was swapped into), so
heapifyrecursively repairs that new location.
How It Works
Here’s the exact sequence I follow inside heapify(A, n, i):
- Assume node $i$ is the (potential) point of violation, and treat it as the current “largest” candidate for now.
- Compute the indices of its left child ($2i+1$) and right child ($2i+2$).
- If the left child exists (is within the heap’s bounds) and its value is greater than the current largest candidate, update the largest candidate to be the left child.
- If the right child exists and its value is greater than the current largest candidate, update the largest candidate to be the right child.
- If the largest candidate is still node $i$ itself, the heap property already holds here — stop, no further action needed.
- Otherwise, swap node $i$ with whichever child was found to be largest.
- Recursively call
heapifyon the index the swap moved the original value into, since that’s now the only place a violation could remain.
Working Principle
The internal logic depends entirely on the assumption that both child subtrees of node $i$ are already valid max-heaps before heapify is called. This assumption is what lets me limit my attention to just three values — node $i$ and its two children — rather than needing to inspect the whole subtree.
Once I identify the true maximum among these three values and swap it into position $i$ (if it wasn’t already there), I’ve guaranteed the heap property holds locally at node $i$. But the value I displaced downward (the original value at node $i$) is now sitting at a child’s former position, and it might still be smaller than that node’s own children. So I recurse one level down, repeating the same three-way comparison — and this process continues until either the displaced value finds a spot where it’s no longer smaller than its children, or it becomes a leaf (with no children to compare against, so it trivially satisfies the property).
Mathematical Foundation
Since heapify follows a single downward path from node $i$ to (at most) a leaf, the number of comparisons and swaps it performs is bounded by the height of the subtree rooted at $i$.
If node $i$ is at height $h$ within the tree (where leaves have height 0), then heapify performs at most $h$ swaps, and at each level it performs a constant number of comparisons (two comparisons to find the largest of three values). So the cost of a single heapify call rooted at height $h$ is:
$$ T_{\text{heapify}}(h) = O(h) $$
Since the maximum possible height in a heap of $n$ elements is $\lfloor \log_2 n \rfloor$, the worst-case cost of any single heapify call (such as one called on the root) is:
$$ T_{\text{heapify}}(n) = O(\log n) $$
I can express this as a simple recurrence as well. If, in the worst case, the recursive call moves into a subtree that could be as large as $\frac{2n}{3}$ (this fraction comes from the fact that the last level of a heap can be incomplete, so the larger of the two child subtrees could hold up to two-thirds of the remaining nodes), the recurrence is:
$$ T(n) \leq T\left(\frac{2n}{3}\right) + O(1) $$
By the Master Theorem (this fits case 2 with $a=1, b=3/2$, and $f(n)=O(1)=O(n^{\log_{3/2} 1})=O(n^0)$):
$$ T(n) = O(\log n) $$
Both derivations agree: a single call to heapify costs $O(\log n)$ in the worst case, or more precisely $O(h)$ where $h$ is the height of the node it’s called on.
Diagrams
Here’s the decision flow within a single heapify call:
flowchart TD
A["heapify(A, n, i)"] --> B["largest = i"]
B --> C{"left child exists and A[left] > A[largest]?"}
C -- Yes --> D["largest = left"]
C -- No --> E{"right child exists and A[right] > A[largest]?"}
D --> E
E -- Yes --> F["largest = right"]
E -- No --> G{"largest != i?"}
F --> G
G -- No --> H["Done: heap property holds at i"]
G -- Yes --> I["Swap A[i] and A[largest]"]
I --> J["Recursively call heapify(A, n, largest)"]And here’s a diagram showing the downward path a displaced element takes through the tree:
flowchart LR
A["Node i (violation)"] --> B["Swap with larger child"]
B --> C["Displaced value now at child's old position"]
C --> D["Compare against new children"]
D --> E{"Still smaller than a child?"}
E -- Yes --> B
E -- No --> F["Sift-down complete"]Pseudocode
HEAPIFY(A, n, i)
largest = i
left = 2*i + 1
right = 2*i + 2
if left < n and A[left] > A[largest]
largest = left
if right < n and A[right] > A[largest]
largest = right
if largest != i
swap A[i] and A[largest]
HEAPIFY(A, n, largest)
Step-by-Step Example
Let me trace through calling heapify on the root (index 0) of the array:
$$ [4, 14, 7, 1, 8, 2] $$
This array is constructed so that only the root violates the heap property — every other parent-child relationship already satisfies it.
Step 1 — Check index 0 (value 4): Left child (index 1) = 14, right child (index 2) = 7. Comparing: $14 > 4$, so largest becomes index 1. Then $7 > 14$? No, so largest stays at index 1. Since largest (1) $\neq$ i (0), I swap indices 0 and 1 → $[14, 4, 7, 1, 8, 2]$.
Step 2 — Recurse to index 1 (value now 4): Left child (index 3) = 1, right child (index 4) = 8. Comparing: $1 > 4$? No. Then $8 > 4$? Yes, so largest becomes index 4. Since largest (4) $\neq$ i (1), I swap indices 1 and 4 → $[14, 8, 7, 1, 4, 2]$.
Step 3 — Recurse to index 4 (value now 4): This node has no children within the array bounds (indices $2(4)+1=9$ and $2(4)+2=10$ are both out of range for a 6-element array). So largest stays as index 4 itself, and the recursion stops.
Final array:
$$ [14, 8, 7, 1, 4, 2] $$
This matches exactly what my tested C program produced, which traced the exact same two swaps (index 0↔1, then index 1↔4) before correctly stopping at the leaf.
Time Complexity
- Best Case: $O(1)$ — occurs when the node already satisfies the heap property relative to its children, requiring no swap and no recursion.
- Average Case: $O(\log n)$ — on average, across many calls (such as during the build-heap or extraction phases), the expected work per call depends on the node’s position, but the worst-case bound per call remains logarithmic.
- Worst Case: $O(\log n)$ — occurs when the displaced element must sift all the way down from the root to a leaf, traversing the full height of the tree.
Space Complexity
A single call to heapify requires:
$$ O(1) $$
auxiliary space for the swap operation itself. If implemented recursively (as I do in my tested code), it additionally requires:
$$ O(\log n) $$
stack space in the worst case, since the recursion depth matches the height of the path traversed. An iterative implementation (using a while loop instead of recursive calls) eliminates this stack usage entirely, achieving strictly $O(1)$ total space.
Correctness Analysis
I prove heapify‘s correctness using the precondition that both child subtrees of node $i$ are already valid max-heaps (this is the assumption under which heapify is always called, both in the build phase and the extraction phase).
Claim: After heapify(A, n, i) completes, the subtree rooted at $i$ is a valid max-heap.
Proof by strong induction on the height of node $i$:
Base case (height 0, a leaf): Node $i$ has no children, so it trivially satisfies the max-heap property on its own — there’s nothing to compare against, and the function’s child-existence checks (left < n, right < n) correctly prevent any action.
Inductive step: Assume the claim holds for all nodes of height less than $h$. Consider a node $i$ at height $h$. By precondition, both of its child subtrees are already valid max-heaps. The function correctly identifies the largest among $A[i]$ and its (up to two) children, via direct comparison. If node $i$’s original value is already the largest, no swap occurs, and the max-heap property already holds at $i$ (since I’ve just confirmed $A[i] \geq$ both children, and the children’s own subtrees were already valid heaps by precondition). If a child is larger, swapping brings the true maximum to the root of this subtree, satisfying the local heap property at $i$. However, this swap moves the original (possibly small) value into the child’s former position, which has height $h-1$ — the recursive call HEAPIFY(A, n, largest) then correctly restores the heap property there, by the inductive hypothesis (since that subtree now has height $h – 1 < h$).
Since the local property holds at $i$ after the swap, and the recursive call guarantees the subtree below is also valid, the entire subtree rooted at $i$ is a valid max-heap once heapify completes. By induction, this holds for nodes of any height, including the root.
Advantages
- Extremely efficient for its scope: $O(\log n)$ worst case to repair a single-point violation, rather than needing to re-examine the entire structure.
- Simple, well-understood logic: compare three values, swap if needed, recurse.
- Reusable across contexts — the exact same procedure powers both heap construction and heap extraction, as well as priority queue operations like
insert(via its sibling operation, sift-up) andextractMax. - Its correctness proof is a clean, standard induction, making it easy to verify and trust.
Disadvantages
- Only handles a single point of violation correctly. If more than one node in the tree violates the heap property simultaneously, calling
heapifyonce on a single index does not guarantee a fully repaired heap — this is exactly whybuildMaxHeapmust call it on every non-leaf node in a specific bottom-up order. - Recursive implementations incur $O(\log n)$ stack overhead, avoidable only by rewriting the function iteratively.
- The three-way comparison (self, left child, right child) has small but non-zero constant overhead per level, which some optimized variants (like the “bottom-up heapsort” technique mentioned in my main Heap Sort article) attempt to reduce.
Applications
- The core repair mechanism inside Heap Sort’s extraction phase, called once per element removed.
- The core repair mechanism inside the bottom-up
buildMaxHeapprocedure, called once per non-leaf node. - The
extractMax(orextractMin) operation in any priority queue implementation, used to restore heap order after moving the last element into the root position. - Any algorithm relying on incremental heap maintenance, such as streaming algorithms that need to maintain a running top-$k$ set using a heap that’s updated one element at a time.
Implementation in C
Here is my tested implementation, with tracing output added to show each comparison and swap explicitly:
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Restores the max-heap property at index i, assuming child subtrees
// are already valid heaps. Traces each comparison and swap for clarity.
void heapify(int arr[], int n, int i, int depth) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
printf("Checking index %d (value %d), left=%d, right=%d\n",
i, arr[i], left < n ? arr[left] : -999, right < n ? arr[right] : -999);
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
printf("Swapping index %d (%d) with index %d (%d)\n", i, arr[i], largest, arr[largest]);
swap(&arr[i], &arr[largest]);
printArray(arr, n);
heapify(arr, n, largest, depth + 1);
} else {
printf("No swap needed at index %d\n", i);
}
}
int main() {
// Array where only the root violates the max-heap property
int arr[] = {4, 14, 7, 1, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Initial array (only root violates heap property): ");
printArray(arr, n);
heapify(arr, n, 0, 0);
printf("Final array: ");
printArray(arr, n);
return 0;
}
Sample Input and Output
Input:
4 14 7 1 8 2
Output (verified by compiling and running the code above):
Initial array (only root violates heap property): 4 14 7 1 8 2
Checking index 0 (value 4), left=14, right=7
Swapping index 0 (4) with index 1 (14)
14 4 7 1 8 2
Checking index 1 (value 4), left=1, right=8
Swapping index 1 (4) with index 4 (8)
14 8 7 1 4 2
Checking index 4 (value 4), left=-999, right=-999
No swap needed at index 4
Final array: 14 8 7 1 4 2
(Note: the -999 values printed for the final check simply indicate “no child exists at this index” in my tracing code — they aren’t part of the actual array data.)
Optimization Techniques
- Iterative rewrite: Converting the recursive calls into a
whileloop removes stack overhead entirely, which matters in performance-critical or embedded contexts. - Reducing comparisons via the “bottom-up” heapify variant: Instead of comparing the current node against both children at every level, this variant first finds the path of always-larger children down to a leaf, then uses a binary search along that path to find where the displaced element belongs — reducing the total comparisons from roughly $2\log n$ down to about $\log n$ in the typical case.
- Branch prediction friendliness: Structuring the child-existence checks (
left < n,right < n) to be predictable can help modern CPUs pipeline these comparisons more efficiently, though this is a micro-optimization that matters mainly at very large scale. - Caching child indices: Some implementations precompute or cache
2*i+1and2*i+2to avoid redundant arithmetic, though compilers typically optimize this automatically in modern C.
Common Mistakes
- Calling
heapifyon a node whose children are not yet valid heaps. This violates the precondition the whole correctness proof depends on, and will not correctly repair the structure — this is why the bottom-up order inbuildMaxHeapis essential, not optional. - Forgetting to check child bounds (
left < n,right < n) before accessing them. Skipping this check can read out-of-bounds memory or, in the extraction context, incorrectly compare against elements that have already been moved into the “sorted” region. - Comparing only the left child, forgetting the right child (or vice versa), which can leave the heap property violated if the untested child was actually the larger of the two.
- Not recursing after a swap. A common bug is performing the single swap correctly but forgetting to call
heapifyagain on the new position, leaving a potential violation one level deeper unaddressed. - Assuming a single
heapifycall can fix a heap with multiple simultaneous violations. This function is only designed to fix one violation point at a time — multiple violations require a full re-run ofbuildMaxHeap, not repeated single calls toheapifyat arbitrary indices.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), MIT Press — https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- J.W.J. Williams, “Algorithm 232 – Heapsort”, Communications of the ACM, 1964 — https://dl.acm.org/doi/10.1145/512274.512284
- Wikipedia, “Binary heap” — https://en.wikipedia.org/wiki/Binary_heap
- Wikipedia, “Heapsort” — https://en.wikipedia.org/wiki/Heapsort
- Visualgo, Heap Visualization — https://visualgo.net/en/heap
