Heap Sort in C: Build, Extract, Trace and Safe Indices

Heap sort in C first turns an array into a max-heap, then repeatedly moves the maximum to the end and restores the heap in the remaining prefix. A max-heap puts every parent at least as high as its children; it is not a fully sorted array. The iterative implementation below sorts ascending in place with O(n log n) worst-case time and O(1) auxiliary storage.

Complete heap-sort program

With zero-based indexing, a node at index r has a left child at 2r + 1 and a right child at 2r + 2, if those indices exist. The code checks whether a left child exists before calculating that index. It then chooses the larger child, swapping only if the heap property is violated.

#include <stdio.h>
#include <stddef.h>

static void sift_down(int values[], size_t count, size_t root) {
    /* Only indices below count / 2 have a left child. */
    while (root < count / 2) {
        size_t child = root * 2 + 1;
        if (child + 1 < count && values[child] < values[child + 1]) ++child;
        if (values[root] >= values[child]) return;
        int temporary = values[root];
        values[root] = values[child];
        values[child] = temporary;
        root = child;
    }
}

void heap_sort(int values[], size_t count) {
    if (count < 2) return;
    for (size_t parent = count / 2; parent > 0;) {
        --parent;
        sift_down(values, count, parent);
    }
    for (size_t end = count - 1; end > 0; --end) {
        int temporary = values[0];
        values[0] = values[end];
        values[end] = temporary;
        sift_down(values, end, 0);
    }
}

int main(void) {
    int values[] = {64, 34, 25, 12, 22};
    size_t count = sizeof values / sizeof values[0];
    heap_sort(values, count);
    for (size_t i = 0; i < count; ++i) {
        printf("%s%d", i == 0 ? "" : " ", values[i]);
    }
    putchar('\n');
    return 0;
}

12 22 25 34 64

Two stages: build and extract

Build: start with the last parent (count / 2 - 1) and sift parents downward in reverse order. Leaves are already heaps of size one. The loop decrements only when parent > 0, avoiding unsigned underflow; an unsigned countdown written i >= 0 would never terminate normally.

Extract: swap the root maximum with the last heap element. Shorten the heap by one and sift the replacement root down. The sorted suffix is no longer part of the heap and must not be touched by sift_down.

Trace the sample array

This particular input already satisfies the max-heap property, so construction makes no swaps. That does not mean it is sorted. To see construction do work, try {1, 2, 3, 4, 5}: bottom-up construction yields 5 4 3 1 2 with this child-selection rule.

Complexity and stability

Bottom-up heap construction is O(n), not O(n log n): most nodes are near the leaves and can travel only a short distance. There are O(n / 2^(h+1)) nodes of height h, and summing their possible sift distances gives a linear bound. Building a heap by inserting one element at a time is a different construction with O(n log n) worst-case work.

Extraction makes n − 1 root removals, each with O(log n) worst-case sift work, so the complete sort has O(n log n) worst-case time. Under the usual distinct-key model its best/average behavior is also described as O(n log n); with this early-return sift, all-equal input can finish in O(n). A blanket tight best-case Θ(n log n) claim for every allowed input would be inaccurate. O(n log n) remains a valid upper bound for all inputs.

The shown sift is iterative, so it needs O(1) auxiliary space. A recursive sift would use call-stack space. Heap sort is not stable: root/end swaps can change the relative order of equal-key records. For example, the identities in 2a 2b 1 need not remain in their original order. Use a stable algorithm or include original position in the comparison when that ordering matters.

Array contract and tests to try

The function modifies count writable integers in place. The caller supplies the length; sizeof can calculate that length in main, where values is an array, but not from an array parameter, which adjusts to a pointer. With count zero the function touches nothing and permits a null pointer; positive counts require a valid array. Do not create a nonstandard zero-length array to test empty input.

No stdin is needed. Edit the initializer and run again: {3, -1, 3, 0} should become -1 0 3 3; {2, 2, 2} stays unchanged. Also test one element, ascending order, reverse order and integer extremes. The comparisons do not subtract two integers, so they do not introduce signed overflow when comparing INT_MIN with INT_MAX.

The expected output is a reference, not a fresh compiler execution. The run link loads the exact displayed program and clears old stdin. See arrays for indexing and program structure for the role of headers, functions and main.

Boundary safety and practice

root < count / 2 establishes that a child exists and that root * 2 + 1 is within the count before evaluating it. child + 1 < count checks the right child before reading it. Calls with counts 0 or 1 return immediately. During extraction, end is the exclusive heap size passed to sift, not the last heap index.

Draw the array {4, 1, 3, 2} as a binary tree. After construction it is 4 2 3 1. Predict each extraction, then run the program. Compare selection sort: both repeatedly select a maximum or minimum, but a heap avoids scanning the entire remaining array for every selection.

For trade-offs among stable sorts, in-place sorts and quadratic teaching algorithms, use the sorting algorithms guide.

Frequently asked questions

Is a heap the same as the dynamically allocated heap?

No. A binary heap is a tree-shaped ordering of elements, often stored in an array. The memory region used by malloc is also called the heap, but that is a different concept. This program does not allocate dynamic memory.

Why is heap sort not always the fastest O(n log n) sort?

Asymptotic bounds do not capture cache behavior, constants, comparison costs or data distribution. Choose from measured workloads and requirements, not a universal speed ranking.