Heap Sort — In-Place Comparison Sorting

What does it solve?

Sorts an array in-place by treating it as a binary heap. First, build a max heap so the root is the largest element. Then repeatedly swap the root with the last unsorted element and restore the heap property.

Key insight: after each extraction, the heap shrinks by one and the sorted portion at the end grows by one. The heapify operation runs in O(log N), and we do it N times: total O(N log N).

Heap Navigation

// For node at index i:
parent(i) = floor((i - 1) / 2)
left(i) = 2 * i + 1
right(i) = 2 * i + 2

// Max heap property:
arr[parent] >= arr[child]

Interactive Visualization

Comparing

Swapping

Current Node

Sorted

Array:

Array Representation

Binary Heap Tree

Step 0 of 0

Phase

Init

Comparisons

Swaps

Heap Size

Ready. Press Play or Next to start the Heap Sort animation.

✓ Sorted

Speed

Step-by-Step Walkthrough

Phase	Description
1. Build Heap	Starting from last non-leaf, call heapify on each node going upward to build a max heap
2. Heapify	Compare node with children, swap with largest child if needed, recurse down
3. Extract	Swap root (max) with last heap element, reduce heap size, heapify root
4. Sorted	Extracted elements accumulate at the end of the array in sorted order

C++ — Heap Sort

void heapify(vector<int>& arr, int n, int root) {
    int largest = root;
    int left  = 2 * root + 1;
    int right = 2 * root + 2;

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

    if (largest != root) {
        swap(arr[root], arr[largest]);
        heapify(arr, n, largest);  // recurse down
    }
}

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

    // 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--) {
        swap(arr[0], arr[i]);  // move max to end
        heapify(arr, i, 0);   // restore heap
    }
}

Complexity

Time (All Cases)

O(N log N)

Guaranteed O(N log N) in best, average, and worst case.

Space

O(1)

In-place sort. Only constant extra memory needed.

Stable?

Relative order of equal elements is not preserved.

In-Place?

Yes

Sorts within the original array using heap structure.

📝 Notes

▼