Offensive Security Researcher & Quantum Cryptography Analyst

Heap Sort Algorithm: Comprehensive Explanation and C Implementation Guide

Abdul Wahab Junaid
Heap Sort Algorithm: Comprehensive Explanation and C Implementation

I consider Heap Sort one of the most theoretically satisfying sorting algorithms I’ve studied, because it manages to combine two properties that usually seem to be in tension: guaranteed $O(n \log n)$ worst-case performance (something QuickSort can’t promise) and truly in-place sorting with only $O(1)$ auxiliary space (something Merge Sort can’t offer). It achieves this by building on the binary heap data structure I cover in my priority queue article, repurposing it directly as a sorting mechanism.

In this article, I want to give the complete picture of Heap Sort — how it works end to end, why it’s correct, and how it performs — while my two companion articles go deeper into its two internal phases: building a heap and maintaining the heap property.

History and Background

Heap Sort was invented by J.W.J. Williams in 1964, introduced in the same paper (Algorithm 232 – Heapsort, published in Communications of the ACM) that first described the binary heap data structure itself. I find it notable that the heap and Heap Sort were essentially co-invented — the data structure was designed specifically to enable this sorting algorithm.

Shortly after, in 1964, Robert W. Floyd published an improvement to the heap construction phase, showing that a heap could be built from an unsorted array in linear time, $O(n)$, rather than the $O(n \log n)$ that would result from inserting elements one at a time. This refinement — often called “Floyd’s build-heap algorithm” — is the version I implement and analyze in my dedicated article on building a heap, and it’s the version most modern textbooks (including CLRS) present as the standard approach.

Problem Statement

The problem I’m solving is the standard comparison-based sorting problem: given an array of $n$ elements, rearrange them into sorted order. What distinguishes Heap Sort’s approach is that it does this by first imposing a heap structure on the data, then repeatedly extracting the maximum element and shrinking the heap, which naturally produces sorted output when I place each extracted maximum at the end of the shrinking active region.

Core Concepts

How It Works

Here is the full sequence I follow for Heap Sort:

  1. Build a max-heap from the entire unsorted input array, using the bottom-up buildMaxHeap procedure (detailed in my companion article).
  2. Swap the root of the heap (the maximum element, at index 0) with the last element in the current heap region.
  3. Reduce the heap size by one, effectively “removing” that last position from further heap operations — it now holds a correctly placed, sorted element.
  4. Restore the heap property at the new root (which is the element that used to be last) by calling heapify on index 0, using the reduced heap size.
  5. Repeat steps 2–4 until the heap size is reduced to 1, at which point the entire array is sorted.

Working Principle

The internal logic here is a clever repurposing of the priority queue’s extractMax operation, applied directly on the input array itself rather than a separate structure. Every time I move the maximum element to the end of the active heap region and shrink the heap, I’m doing exactly what extractMax does in a priority queue — except instead of discarding the extracted maximum or storing it elsewhere, I let it settle into its final sorted position within the very same array I’m heapifying.

This is what makes Heap Sort in-place: the “sorted” region and the “heap” region share the same underlying array, growing and shrinking respectively from the same fixed block of memory, with no extra allocation needed beyond the array I started with.

Mathematical Foundation

Heap Sort’s total running time is the sum of two phases.

Phase 1 — Build-max-heap: Although a naive analysis might suggest $O(n \log n)$ (since I call heapify, which is $O(\log n)$, on $n/2$ non-leaf nodes), a tighter analysis shows this phase actually runs in:

$$ T_{\text{build}}(n) = O(n) $$

This is because most nodes in a heap are near the bottom, where heapify does very little work, and only a few nodes near the top require work proportional to $\log n$. I derive this bound rigorously in my companion article on building a heap, using the sum:

$$ \sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil O(h) = O(n) $$

Phase 2 — Repeated extraction: I perform $n – 1$ extractions, and each one involves a swap ($O(1)$) followed by a heapify call, which costs $O(\log n)$ in the worst case (bounded by the height of the heap). So this phase costs:

$$ T_{\text{extract}}(n) = \sum_{i=1}^{n-1} O(\log i) = O(n \log n) $$

Total running time:

$$ T(n) = T_{\text{build}}(n) + T_{\text{extract}}(n) = O(n) + O(n \log n) = O(n \log n) $$

The $O(n \log n)$ extraction phase dominates the $O(n)$ build phase, so the overall asymptotic complexity of Heap Sort is:

$$ T(n) = O(n \log n) $$

Diagrams

Here’s the two-phase structure of Heap Sort at a high level:

flowchart TD
    A[Unsorted Array] --> B["Phase 1: Build Max-Heap (O(n))"]
    B --> C["Phase 2: Repeated Extraction (O(n log n))"]
    C --> D[Swap root with last element in heap region]
    D --> E[Shrink heap size by 1]
    E --> F[Heapify at root to restore heap property]
    F --> G{Heap size > 1?}
    G -- Yes --> D
    G -- No --> H[Array is Fully Sorted]

And here’s a diagram showing how the array is conceptually divided during the extraction phase:

flowchart LR
    A["Array of size n"] --> B["Heap region: indices 0 to heapSize-1"]
    A --> C["Sorted region: indices heapSize to n-1"]
    B --> D["Shrinks by 1 each extraction"]
    C --> E["Grows by 1 each extraction, holds final sorted values"]

Pseudocode

HEAP-SORT(A, n)
    BUILD-MAX-HEAP(A, n)

    for i = n - 1 down to 1
        swap A[0] and A[i]
        heapSize = i          // shrink the active heap region
        HEAPIFY(A, heapSize, 0)

HEAPIFY(A, heapSize, i)
    largest = i
    left = 2*i + 1
    right = 2*i + 2

    if left < heapSize and A[left] > A[largest]
        largest = left
    if right < heapSize and A[right] > A[largest]
        largest = right

    if largest != i
        swap A[i] and A[largest]
        HEAPIFY(A, heapSize, largest)

BUILD-MAX-HEAP(A, n)
    for i = floor(n/2) - 1 down to 0
        HEAPIFY(A, n, i)

Step-by-Step Example

Let me trace through the array:

$$ [12, 11, 13, 5, 6, 7] $$

Phase 1 — Build max-heap: After running buildMaxHeap, the array becomes a valid max-heap. Tracing the heapify calls at indices 2, 1, and 0 (as described in my build-heap companion article’s methodology applied to this array), the heap array becomes:

$$ [13, 11, 12, 5, 6, 7] $$

Phase 2 — Repeated extraction:

Iteration $i=5$: Swap root (13) with last element (7) → $[7, 11, 12, 5, 6, 13]$. Heap size shrinks to 5. Heapify at root: 7 vs children 11, 12 → largest is 12 (index 2), swap → $[12, 11, 7, 5, 6, 13]$; 7 (now index 2) has no children within heap size 5, so heapify stops. Array: $[12, 11, 7, 5, 6, 13]$.

Iteration $i=4$: Swap root (12) with element at index 4 (6) → $[6, 11, 7, 5, 12, 13]$. Heap size shrinks to 4. Heapify at root: 6 vs children 11, 7 → largest is 11 (index 1), swap → $[11, 6, 7, 5, 12, 13]$; 6 (now index 1) vs child at index 3 (5) → 6 is already larger, stop. Array: $[11, 6, 7, 5, 12, 13]$.

Iteration $i=3$: Swap root (11) with element at index 3 (5) → $[5, 6, 7, 11, 12, 13]$. Heap size shrinks to 3. Heapify at root: 5 vs children 6, 7 → largest is 7 (index 2), swap → $[7, 6, 5, 11, 12, 13]$.

Iteration $i=2$: Swap root (7) with element at index 2 (5) → $[5, 6, 7, 11, 12, 13]$. Heap size shrinks to 2. Heapify at root: 5 vs child 6 (index 1) → swap → $[6, 5, 7, 11, 12, 13]$.

Iteration $i=1$: Swap root (6) with element at index 1 (5) → $[5, 6, 7, 11, 12, 13]$. Heap size shrinks to 1, loop ends.

Final array:

$$ [5, 6, 7, 11, 12, 13] $$

This matches exactly what my tested C implementation produces.

Time Complexity

Space Complexity

Heap Sort requires only:

$$ O(1) $$

auxiliary space (a constant number of temporary variables for swaps), plus $O(\log n)$ stack space if heapify is implemented recursively (as I do in my C implementation). An iterative version of heapify can reduce this to strictly $O(1)$ total auxiliary space.

Correctness Analysis

I verify correctness in two stages.

Build-max-heap correctness: By induction on the order of processing (from the last non-leaf node up to the root), I know that when heapify is called on any node $i$, both of its child subtrees are already valid max-heaps (this is guaranteed since I process nodes in reverse level order, and leaves are trivially valid heaps of size 1). heapify then correctly restores the heap property at node $i$, so the entire tree rooted at $i$ becomes a valid heap. By the time this process reaches the root, the whole array is a valid max-heap.

Extraction phase correctness: At the start of each iteration, I maintain the invariant that A[0..heapSize-1] is a valid max-heap, and A[heapSize..n-1] contains the largest n - heapSize elements in sorted order. Swapping the root (the current maximum of the heap region) with the last heap element, then shrinking the heap size by one, correctly places that maximum into its correct final sorted position, extending the sorted region by one element while removing it from the heap’s responsibility. Calling heapify on the new root restores the heap property for the now-smaller heap region, preserving the invariant for the next iteration.

By induction, once the heap size reaches 1, the entire array (aside from the single remaining heap element, which is by definition the smallest and correctly placed at index 0) is sorted.

Advantages

Disadvantages

Applications

Implementation in C

Here is my tested, complete implementation:

#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.
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, 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

Common Mistakes

Further Reading

Exit mobile version