Heap Sort

Sort an array in-place using a max-heap — O(n log n) guaranteed, O(1) space.

Heap Sort

Heap Sort uses a max-heap to sort an array in-place. It has two phases:

Build Heap — rearrange the array into a valid max-heap so the largest element is at index 0.
Extract Max repeatedly — swap the root (max) to the end of the unsorted region, shrink the heap by 1, and restore the heap property by sifting the new root down.

After n extractions, the array is sorted in ascending order.

Note

Heap Sort never needs extra memory — it builds the heap inside the original array. Unlike Merge Sort, there's no auxiliary array. Unlike Quick Sort, worst case is always O(n log n).

How It Works — Step by Step

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

Phase 1 — Build Max-Heap

Start from the last non-leaf node (n/2 - 1) and heapify downward to index 0.

Initial:  [4, 10, 3, 5, 1]
           0   1  2  3  4

Heapify index 1: children are 3 (index 3) and 4 (index 4) → 5 > 4, swap
After:    [4, 10, 3, 5, 1]  → [4, 10, 3, 5, 1]   (5 > 1, no change needed at i=1... wait, 10 > both children, no swap)

Heapify index 0: children are 10 (index 1) and 3 (index 2) → 10 > 4, swap
After:    [10, 4, 3, 5, 1]
           Then heapify index 1: children 5 and 1 → 5 > 4, swap
Final:    [10, 5, 3, 4, 1]   ← valid max-heap

Phase 2 — Extract Max (repeat n-1 times)

Step 1: Swap root with last → [1, 5, 3, 4, | 10]
        Heapify down index 0 → [5, 4, 3, 1, | 10]

Step 2: Swap root with last → [1, 4, 3, | 5, 10]
        Heapify down → [4, 1, 3, | 5, 10]

Step 3: Swap → [3, 1, | 4, 5, 10]
        Heapify → [3, 1, | 4, 5, 10]

Step 4: Swap → [1, | 3, 4, 5, 10]

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

Time & Space Complexity

Phase	Time	Why
Build Heap	`O(n)`	Bottom-up heapify is O(n) — not O(n log n)
Extract Max × n	`O(n log n)`	n swaps, each heapify-down is O(log n)
Total	`O(n log n)`	All cases — no worst-case degradation
Space	`O(1)`	In-place, no auxiliary array

Note

Heap Sort is not stable — equal elements may change relative order. Use Merge Sort if stability is required.

Code

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

// Restore the max-heap property for subtree rooted at index i
// n = current heap size (elements after index n are already sorted)
void heapifyDown(vector<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]);
        heapifyDown(arr, n, largest); // Fix the affected subtree
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // Phase 1: Build max-heap (bottom-up, O(n))
    // Last non-leaf is at index n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--)
        heapifyDown(arr, n, i);

    // Phase 2: Extract max one by one
    for (int end = n - 1; end > 0; end--) {
        swap(arr[0], arr[end]);   // Move current max to end
        heapifyDown(arr, end, 0); // Restore heap on reduced range
    }
}

// Example:
// arr = {4, 10, 3, 5, 1}  →  {1, 3, 4, 5, 10}

Why O(n) for Build Heap?

It seems like calling heapify on n/2 nodes, each taking O(log n), should give O(n log n). But most nodes are near the bottom of the tree where heapify takes only O(1) or O(2) steps. The exact sum works out to O(n).

Intuitively: half the nodes are leaves (0 work), a quarter are one level up (1 swap max), an eighth are two levels up, and so on. The geometric series converges to O(n).

Heap Sort vs Other O(n log n) Algorithms

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

Heap Sort is the only comparison sort that guarantees O(n log n) and O(1) space. In practice, Quick Sort is faster due to better cache locality — Heap Sort jumps around the array in a pattern that misses CPU caches frequently.