Offensive Security Researcher & Quantum Cryptography Analyst

Heap Sort Algorithm: A Detailed Explanation and Implementation in C

Abdul Wahab Junaid
Heap Sort: A Detailed Explanation and Implementation in C

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

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:

  1. heapify(arr, n, i) — the shared repair function, called with different n values depending on context (full array size during build, shrinking heap size during extraction).
  2. buildMaxHeap(arr, n) — loops from the last non-leaf index down to 0, calling heapify at each step, transforming the raw array into a valid max-heap.
  3. heapSort(arr, n) — the top-level driver, which first calls buildMaxHeap, then loops from the end of the array back to index 1, swapping the root with the current last heap element and calling heapify on the shrunk heap each time.
  4. 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.-> F

And 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:

  1. heapSort(arr, 6) is called.
  2. This immediately calls buildMaxHeap(arr, 6), which internally calls heapify(arr, 6, 2), then heapify(arr, 6, 1), then heapify(arr, 6, 0) — transforming the array into a valid max-heap: $[13, 11, 12, 5, 6, 7]$.
  3. Control returns to heapSort, which begins its extraction loop. For $i=5$: swap root and index 5, then call heapify(arr, 5, 0) — note the size parameter is now 5, not 6, correctly excluding the just-placed sorted element at index 5.
  4. This pattern continues for $i=4, 3, 2, 1$, with the size parameter passed to heapify shrinking each time, until the array is fully sorted.

Time Complexity

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:

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

Disadvantages

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:

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:

Further Reading

Exit mobile version