Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. Its standout property: it is guaranteed O(n log n) in all cases — best, average, and worst — while using only O(1) extra memory. No Quick Sort worst-case surprises, no Merge Sort extra array.

Key Concept — The Max-Heap

A max-heap is a complete binary tree where every parent is greater than or equal to its children. Stored as an array, the relationships are:

• Parent of node i: (i - 1) / 2
• Left child of i: 2 * i + 1
• Right child of i: 2 * i + 2

Array:  [10,  5,  3,  4,  1]
Index:    0   1   2   3   4

Tree view:
       10          ← root = largest element
      /  \
     5    3
    / \
   4   1

The root of a max-heap is always the largest element — Heap Sort exploits this to extract elements in descending order.

Algorithm — Two Phases

1. Build max-heap — rearrange the unsorted array into a valid max-heap. O(n).
2. Extract max repeatedly — swap root (largest) to the end of the array, shrink the heap by one, restore the heap property. Repeat n-1 times. O(n log n).

Step-by-Step Example

Sort [4, 10, 3, 5, 1]:

Initial array: [4, 10, 3, 5, 1]

── Phase 1: Build Max-Heap ──
Start at last non-leaf (index 1, value 10):
  10 > children (5, 1) → no swap

Move to index 0 (value 4):
  4 < 10 → swap → [10, 4, 3, 5, 1]
  Sift 4 down: 4 < 5 → swap → [10, 5, 3, 4, 1]

Max-heap built: [10, 5, 3, 4, 1]

── Phase 2: Extract ──
Swap root with last → [1, 5, 3, 4, | 10]  sift down 1 → [5, 4, 3, 1, | 10]
Swap root with last → [1, 4, 3, | 5, 10]  sift down 1 → [4, 1, 3, | 5, 10]
Swap root with last → [3, 1, | 4, 5, 10]  sift down 3 → [3, 1, | 4, 5, 10]
Swap root with last → [1, | 3, 4, 5, 10]

Final: [1, 3, 4, 5, 10] ✓

C Program — Heap Sort

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* Restore max-heap property at index i in a heap of size n */
void sift_down(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]);
        sift_down(arr, n, largest);
    }
}

/* Build a max-heap in-place — O(n) */
void build_heap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        sift_down(arr, n, i);
}

void heapsort(int arr[], int n) {
    build_heap(arr, n);

    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);  /* move current max to sorted end */
        sift_down(arr, i, 0);    /* restore heap over remaining elements */
    }
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter %d elements: ", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Before sorting: ");
    print_array(arr, n);

    heapsort(arr, n);

    printf("After sorting:  ");
    print_array(arr, n);

    return 0;
}

Code Explanation

• sift_down(arr, n, i) — looks at node i and its two children. If either child is larger, swaps the node with the largest child and recurses downward. This restores the max-heap property from i down to the leaves.
• build_heap() — starts from the last non-leaf node (n/2 - 1) and calls sift_down() going backwards to index 0. Bottom-up construction is O(n) — more efficient than inserting elements one by one.
• heapsort() — after building the heap, repeatedly swaps arr[0] (the max) with the last unsorted element, then shrinks the heap by 1 and calls sift_down() to restore the heap over the remaining elements.

Sample Output

Enter number of elements: 6
Enter 6 elements: 4 10 3 5 1 8
Before sorting: 4 10 3 5 1 8
After sorting:  1 3 4 5 8 10

Time and Space Complexity

Heap Sort vs Other Sorting Algorithms

Heap Sort's unique position: it matches Merge Sort's worst-case guarantee (always O(n log n)) while matching Quick Sort's space efficiency (O(1) extra memory). In practice Quick Sort is faster on average due to better cache behaviour, but Heap Sort is the right choice when you need a hard worst-case bound without allocating extra memory.

Real-World Applications

• Priority queues — the heap structure itself (not just the sort) is used everywhere: OS schedulers, Dijkstra's shortest path, Huffman coding
• Order statistics — finding the k-th largest element in O(n + k log n)
• Embedded/real-time systems — guaranteed O(n log n) with no extra memory suits constrained environments
• External sorting — heap-based merge in k-way merge sort

Related Sorting Programs in C

• Quick Sort in C — faster in practice, O(n²) worst case
• Merge Sort in C — stable, O(n log n) guaranteed, needs O(n) space
• Insertion Sort in C — best for small or nearly-sorted arrays
• Bubble Sort in C
• Selection Sort in C

As an Amazon Associate we earn from qualifying purchases.

Further Reading

The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.