I’ve already covered Heap Sort’s overall structure, its build phase, and its heap-repair mechanism in three separate articles. In this one, I want to zoom in specifically on the implementation itself — walking through the C code line by line, discussing the engineering decisions behind it, and treating this as the practical, hands-on companion to the more theoretical discussions elsewhere in this series. My goal here is that anyone reading this article alone, without the others, could still implement Heap Sort correctly from scratch.
History and Background
I’ve discussed the origins of Heap Sort in depth elsewhere in this series — J.W.J. Williams’ original 1964 paper and Robert Floyd’s efficiency improvement that same year — so I won’t repeat the full history here. What I do want to highlight in this article is how Heap Sort’s implementation has evolved in practice since then: the core algorithm from 1964 is essentially what I still write in C today, which is a rare kind of longevity in software. Many other algorithms from that era have been superseded or significantly modified, but Heap Sort’s fundamental implementation pattern — build phase, then extraction loop, with a shared heapify helper — has remained the standard approach for six decades.
Problem Statement
The problem I’m solving is, again, the general sorting problem: rearranging $n$ elements into sorted order. But my focus in this article is specifically on the engineering of a correct, efficient, in-place implementation — handling array indexing correctly, structuring the code so heapify can be reused across both phases, and avoiding the common implementation pitfalls that I’ve seen trip people up (and that I list later in this article).
Core Concepts
- Zero-indexed array-to-tree mapping: For a node at array index $i$, its parent is at $\lfloor (i-1)/2 \rfloor$, its left child is at $2i+1$, and its right child is at $2i+2$. Getting this arithmetic right is foundational to every other part of the implementation.
- Shared
heapifysubroutine: Both the build phase and the extraction phase call the exact sameheapifyfunction — good implementations avoid duplicating this logic. - Heap size vs. array length: During extraction, I pass a shrinking size parameter to
heapify(not the full array length), which is what lets already-sorted elements at the end of the array stay untouched by future heap operations. - In-place operation: The entire algorithm operates on a single array passed by reference (a pointer, in C), with no separate output buffer.
How It Works
Since I’ve detailed the algorithmic steps in my main Heap Sort article, here I want to describe how those steps map onto the actual functions in my implementation:
heapify(arr, n, i)— the shared repair function, called with differentnvalues depending on context (full array size during build, shrinking heap size during extraction).buildMaxHeap(arr, n)— loops from the last non-leaf index down to 0, callingheapifyat each step, transforming the raw array into a valid max-heap.heapSort(arr, n)— the top-level driver, which first callsbuildMaxHeap, then loops from the end of the array back to index 1, swapping the root with the current last heap element and callingheapifyon the shrunk heap each time.printArray(arr, n)— a utility function I use purely for demonstrating and verifying output, not part of the sorting logic itself.
Working Principle
What I want to emphasize in this article is the code-level reason the algorithm works: because heapify takes an explicit size parameter rather than assuming it always operates on the full array, I can reuse the exact same function for two very different purposes. During the build phase, n is the full array size, since I want heapify to consider the whole array as live heap data. During extraction, I pass a shrinking value (i, decrementing each loop iteration) so that elements already placed in their final sorted position — which live past index i — are correctly excluded from any further heap comparisons or swaps.
This single design decision (parameterizing the heap size rather than hardcoding it) is what makes the whole implementation clean and avoids needing two separate, near-duplicate versions of the repair logic.
Mathematical Foundation
I’ve derived the complexity bounds in detail in my other Heap Sort articles, so here I’ll summarize the results as they apply directly to this implementation:
$$ T_{\text{buildMaxHeap}}(n) = O(n) $$
$$ T_{\text{extraction loop}}(n) = \sum_{i=1}^{n-1} O(\log i) = O(n \log n) $$
$$ T_{\text{heapSort}}(n) = O(n) + O(n \log n) = O(n \log n) $$
One implementation-specific detail worth noting mathematically: since my heapify function is recursive, each call to it consumes stack frames proportional to the height of the subtree it’s repairing. The maximum recursion depth across the entire algorithm’s execution is therefore:
$$ O(\log n) $$
which is the space cost I account for separately from the $O(1)$ cost of the swap-based in-place data manipulation itself.
Diagrams
Here’s a diagram showing how the three main functions in my implementation relate to each other:
flowchart TD
A["heapSort(arr, n)"] --> B["buildMaxHeap(arr, n)"]
B --> C["heapify(arr, n, i) for i = n/2-1 downto 0"]
A --> D["Extraction loop: for i = n-1 downto 1"]
D --> E["swap(arr[0], arr[i])"]
E --> F["heapify(arr, i, 0)"]
F --> D
C -.shared function.-> FAnd a diagram showing the parameter difference that lets heapify serve both phases:
flowchart LR
A["heapify(arr, size, index)"] --> B["Build phase: size = n (full array)"]
A --> C["Extraction phase: size = shrinking i"]
B --> D["Considers entire array as heap"]
C --> E["Excludes already-sorted tail elements"]Pseudocode
// Shared repair function used by both phases
HEAPIFY(A, size, i)
largest = i
left = 2*i + 1
right = 2*i + 2
if left < size and A[left] > A[largest]
largest = left
if right < size and A[right] > A[largest]
largest = right
if largest != i
swap A[i] and A[largest]
HEAPIFY(A, size, largest)
// Build phase: size parameter is fixed at n
BUILD-MAX-HEAP(A, n)
for i = floor(n/2) - 1 down to 0
HEAPIFY(A, n, i)
// Top-level driver combining both phases
HEAP-SORT(A, n)
BUILD-MAX-HEAP(A, n)
for i = n - 1 down to 1
swap A[0] and A[i]
HEAPIFY(A, i, 0) // size parameter shrinks here
Step-by-Step Example
I’ve already walked through a full trace of this exact algorithm, with every intermediate array state, in my main Heap Sort article, using the input array $[12, 11, 13, 5, 6, 7]$, which sorts correctly to $[5, 6, 7, 11, 12, 13]$. Rather than repeat that full trace here, I want to use this section to highlight the specific function calls that occur, mapped to the implementation:
heapSort(arr, 6)is called.- This immediately calls
buildMaxHeap(arr, 6), which internally callsheapify(arr, 6, 2), thenheapify(arr, 6, 1), thenheapify(arr, 6, 0)— transforming the array into a valid max-heap: $[13, 11, 12, 5, 6, 7]$. - Control returns to
heapSort, which begins its extraction loop. For $i=5$: swap root and index 5, then callheapify(arr, 5, 0)— note the size parameter is now 5, not 6, correctly excluding the just-placed sorted element at index 5. - This pattern continues for $i=4, 3, 2, 1$, with the size parameter passed to
heapifyshrinking each time, until the array is fully sorted.
Time Complexity
- Best Case: $O(n \log n)$
- Average Case: $O(n \log n)$
- Worst Case: $O(n \log n)$
As discussed in my main article, Heap Sort has no pathological worst case — its performance is essentially the same across all input distributions, since the heap height is always $O(\log n)$ regardless of the specific values being sorted.
Space Complexity
For this specific implementation:
- The sort itself uses $O(1)$ auxiliary space for variable storage and swaps.
- The recursive
heapifycalls add $O(\log n)$ stack space in the worst case. - No separate output array is allocated — everything happens within the original input array.
Total: $O(\log n)$ due to recursion, or $O(1)$ if I were to rewrite heapify iteratively.
Correctness Analysis
I’ve provided detailed, separate correctness proofs for the build phase (in my building-a-heap article) and the extraction/heapify mechanism (in my maintaining-the-heap-property article). Here, I want to focus specifically on why the composition of these two phases, as implemented in heapSort, is correct.
The key invariant I maintain across the extraction loop is: at the start of each iteration with loop variable $i$, arr[0..i] is a valid max-heap, and arr[i+1..n-1] contains the $n – i – 1$ largest elements from the original array, already in their correct final sorted positions.
This invariant holds initially (after buildMaxHeap, with $i = n-1$, the sorted region is empty and the whole array is a valid heap). Each iteration swaps the current heap’s maximum (the root) into position $i$ (extending the sorted region by one), then calls heapify(arr, i, 0) — using the new, shrunk size — to restore the heap property on arr[0..i-1]. This directly re-establishes the invariant for the next (smaller) value of $i$.
Since the invariant holds at the start of every iteration, and the loop terminates when $i$ reaches 0 (meaning the heap region has shrunk to a single element, trivially sorted), the entire array arr[0..n-1] must be sorted upon completion.
Advantages
- The implementation cleanly separates concerns: one function for repair (
heapify), one for construction (buildMaxHeap), and one as the top-level driver (heapSort) — this makes the code easy to test and reason about piece by piece. - Reusing
heapifyacross both phases avoids code duplication and keeps the implementation compact. - The parameterized heap-size approach generalizes well — the same
heapifyfunction could be lifted directly into a standalone priority queue implementation with no changes. - In-place operation means this implementation has minimal memory footprint, well-suited to systems programming contexts where C is commonly used.
Disadvantages
- The recursive implementation of
heapify, while clean to read, isn’t the most performant choice for extremely large arrays where stack overhead matters — an iterative version would be preferable in that context. - As with all Heap Sort implementations, this one is not stable, and adapting it to be stable would require additional bookkeeping (like storing original indices alongside values) that complicates the otherwise clean code.
- The implementation assumes plain
intarrays; generalizing it to sort arbitrary data types would require either C’s function-pointer-based comparator pattern (similar to the standard library’sqsort) or a rewrite using macros orvoid*pointers with an explicit element size, both of which add complexity.
Applications
I’ve covered general applications of Heap Sort in my main article. From an implementation perspective specifically, this style of code — a shared repair function driven by two higher-level phases — is a pattern I’ve found reusable well beyond sorting: it’s the same structural approach I’d use to implement a binary heap-backed priority queue (as in my dedicated priority queue article), a k-way merge utility, or a top-k selection routine.
Implementation in C
Here is my complete, tested implementation once more, presented here as the central focus of this article rather than as a supporting example:
#include <stdio.h>
// Swaps two integers via pointers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Restores the max-heap property at index i, assuming subtrees
// rooted at its children are already valid max-heaps.
// The "size" parameter lets this same function serve both the
// build phase (size = n) and the extraction phase (size shrinks).
void heapify(int arr[], int size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && arr[left] > arr[largest])
largest = left;
if (right < size && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, size, largest); // repair the affected subtree
}
}
// Converts an arbitrary array into a valid max-heap in O(n) time
void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
// Full Heap Sort: build a max-heap, then repeatedly extract the max
void heapSort(int arr[], int n) {
buildMaxHeap(arr, n);
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]); // move current max to its sorted position
heapify(arr, i, 0); // restore heap property on the shrunk heap
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
printArray(arr, n);
heapSort(arr, n);
printf("After sorting: ");
printArray(arr, n);
return 0;
}
Sample Input and Output
Input:
12 11 13 5 6 7
Output (verified by compiling and running the code above):
Before sorting: 12 11 13 5 6 7
After sorting: 5 6 7 11 12 13
Optimization Techniques
I’ve covered algorithmic optimizations (iterative heapify, bottom-up variant, d-ary heaps) in my other Heap Sort articles. Here I want to add a few implementation-level engineering practices I follow:
- Minimizing pointer dereferences: In performance-critical C code, caching
arr[i]in a local variable before repeated use can help the compiler optimize more aggressively, though modern compilers often do this automatically. - Using
restrict-qualified pointers (a C99 feature) when the array parameter is guaranteed not to alias with any other pointer in scope, which can help the compiler generate more efficient code. - Compiling with optimization flags (
-O2or-O3with gcc) rather than relying on the algorithm alone, since compiler-level optimizations often meaningfully affect real-world performance for tight loops likeheapify. - Profiling before optimizing: I always recommend measuring actual performance on realistic data before applying micro-optimizations, since the asymptotic behavior ($O(n \log n)$) won’t change, and most of these techniques only affect constant factors.
Common Mistakes
Beyond the mistakes I cover in my other Heap Sort articles (wrong heap size during extraction, incorrect build-phase starting index, assuming stability), here are implementation-specific pitfalls I want to highlight:
- Passing the wrong size parameter to
heapify. Sinceheapifyis reused across two different contexts, it’s easy to accidentally passn(the full array length) during the extraction phase instead of the correctly shrinkingi, which silently breaks the sorted-region invariant. - Not testing the implementation on edge cases like empty arrays ($n=0$) or single-element arrays ($n=1$), which can expose off-by-one errors in loop bounds that don’t show up on larger test inputs.
- Ignoring compiler warnings. Compiling with
-Wall(as I do when testing my own code) surfaces subtle bugs like uninitialized variables or implicit type conversions that might otherwise go unnoticed until they cause a real failure. - Forgetting to free dynamically allocated memory in variants of this code that use
mallocfor the array (rather than a fixed-size stack array as in my example), leading to memory leaks in larger programs that callheapSortrepeatedly.
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
- R.W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM, 1964 — https://dl.acm.org/doi/10.1145/355588.365103
- Wikipedia, “Heapsort” — https://en.wikipedia.org/wiki/Heapsort
- cppreference, “restrict type qualifier” — https://en.cppreference.com/w/c/language/restrict
