Heap Sort in C, C++, and Java: Step-by-Step Guide

Heap sort builds a max heap from the input array and repeatedly extracts the maximum element, sorting in place in O(n log n) time for all cases.

This guide walks through the max-heap property, traces the full build-and-extract sequence on [12, 11, 13, 5, 6, 7], and provides clean working code in C, C++, and Java. A complexity table and a placement-interview quick-reference close the article.

How a Max Heap Works

A binary heap is a complete binary tree stored as an array. According to the Wikipedia article on heap data structures, the two heap variants are the max heap (every parent is greater than or equal to its children) and the min heap (every parent is less than or equal to its children). Heap sort uses the max heap.

For a node at index i in a zero-indexed array:

• Left child is at index 2*i + 1
• Right child is at index 2*i + 2
• Parent of a node at index j is at index (j - 1) / 2 (integer division)

The heapify function enforces the max-heap property at a single node. It finds the largest value among the node, its left child, and its right child, then swaps the node with the largest child if the heap property is violated. It repeats this downward until no further swap is needed.

Building a Max Heap: Traced on [12, 11, 13, 5, 6, 7]

Starting from the last internal node (n/2 - 1 = 2), heapify is called on every node down to the root. The array has six elements, so internal nodes are at indices 2, 1, and 0.

• Index 2 (value 13): left child = index 5 (value 7). 7 < 13, no swap. Array unchanged: [12, 11, 13, 5, 6, 7].
• Index 1 (value 11): left = index 3 (value 5), right = index 4 (value 6). Both 5 < 11 and 6 < 11. No swap.
• Index 0 (value 12): left = index 1 (value 11), right = index 2 (value 13). 13 > 12, so swap index 0 with index 2. Array becomes [13, 11, 12, 5, 6, 7]. Recurse at index 2: left = index 5 (value 7), 7 < 12, no swap.

Max heap after build phase: [13, 11, 12, 5, 6, 7]. The largest element, 13, is at the root.

Extraction phase (each step swaps root with last unsorted element, then re-heapifies):

• Step 1: Swap arr[0] with arr[5]. Array: [7, 11, 12, 5, 6, | 13]. Heapify root with heap size 5. Largest child of 7 is 12 at index 2. Swap. Then heapify index 2: left = index 5, which is outside heap size. Array: [12, 11, 7, 5, 6, | 13].
• Step 2: Swap arr[0] with arr[4]. Array: [6, 11, 7, 5, | 12, 13]. Heapify root: largest child is 11 at index 1. Swap. Heapify index 1: left = index 3 (value 5), 5 < 6, no swap. Array: [11, 6, 7, 5, | 12, 13].
• Steps 3–5 continue the same pattern until the array is fully sorted: [5, 6, 7, 11, 12, 13].

Heap Sort Code in C, C++, and Java

Each implementation uses the same two-function structure: heapify restores the heap property at a node, and heapSort orchestrates the build and extraction phases.

C

#include <stdio.h>

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) {
        int temp      = arr[i];
        arr[i]        = arr[largest];
        arr[largest]  = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    /* Build max heap */
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    /* Extract elements one by one */
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0]   = arr[i];
        arr[i]   = temp;
        heapify(arr, i, 0);
    }
}

int main(void) {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n     = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);   /* Output: 5 6 7 11 12 13 */
    return 0;
}

C++

The C++ version replaces the manual swap with std::swap from <algorithm>. The cppreference documentation for std::make_heap shows the standard library’s own max-heap construction, which is equivalent to the loop below but operating on iterators.

#include <iostream>
#include <algorithm>
using namespace std;

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);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n     = 6;
    heapSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";   // Output: 5 6 7 11 12 13
    cout << endl;
    return 0;
}

Java

Java’s version swaps through a temporary variable. Arrays.toString() formats the output.

import java.util.Arrays;

public class HeapSort {

    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) {
            int temp       = arr[i];
            arr[i]         = arr[largest];
            arr[largest]   = temp;
            heapify(arr, n, largest);
        }
    }

    void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0]   = arr[i];
            arr[i]   = temp;
            heapify(arr, i, 0);
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        HeapSort ob = new HeapSort();
        ob.heapSort(arr);
        System.out.println(Arrays.toString(arr));   // [5, 6, 7, 11, 12, 13]
    }
}

Time and Space Complexity

Algorithm	Best Case	Average Case	Worst Case	Space	Stable
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes

Heap sort’s O(n log n) worst case is its main advantage over quick sort. Quick sort degrades to O(n²) when the pivot is the minimum or maximum element at every partition step, which happens on already-sorted or reverse-sorted data with a naive last-element pivot strategy. Heap sort avoids that entirely.

The O(1) space comes from sorting in place. No auxiliary array is allocated, unlike merge sort which needs an O(n) buffer. The recursive heapify call uses O(log n) stack frames, but an iterative version (replace the recursive call with a while loop descending toward the leaf) reduces that to O(1) as well.

Heap sort is not stable. During extraction, the root is swapped with the last unsorted element, potentially moving one equal-value element across another. If stability matters (for example, sorting by last name then by first name), use merge sort instead.

Heap Sort in Placement Interviews

Technical rounds at companies that include DSA questions regularly test heap sort and heapify. The angles that appear most often:

• Trace one step of heapify on a given array and state the resulting array.
• State the time complexity and explain why the worst case is O(n log n) rather than O(n²).
• Compare heap sort with quick sort and merge sort — interviewers want to hear about the stability and space trade-offs, not just the asymptotic bounds.
• Explain why building a max heap from scratch by calling heapify from n/2 - 1 down to 0 is O(n), even though each heapify call is O(log n). The key insight is that most nodes are near the leaves and heapify terminates quickly for them.

The 20 most-asked data structures interview questions covers heap sort alongside BST traversals and linked-list operations, all of which appear in the same technical-round format.

For practice building comfort with array indexing, finding the smallest and largest element in an array builds the single-scan reasoning that the heapify loop depends on. The flower sticks arrangement problem applies a similar index-based sorting logic in a placement-style problem context.

The O(1) space guarantee makes heap sort the natural backbone for priority queues in production systems. Those queues appear in task schedulers, operating system process managers, and, increasingly, LLM inference engines that sort incoming prompt requests by token budget. TinkerLLM at ₹299 is a hands-on starting point for applying the same data-structure intuitions (heaps, queues, and sorted traversals) to live LLM API calls.