Heap Sort

The idea

Heap sort uses a binary heap — specifically a max-heap, where every parent is ≥ its children, so the biggest value is always at the root.

1. Build a max-heap out of the array.
2. The largest value is now at a[0]. Swap it with the last element of the heap — it’s now in its final position.
3. Shrink the heap by one and sift the new root down to restore the heap rule.
4. Repeat until the heap is empty. The array is sorted, smallest to largest.

The 3D model shows the heap as a tree (top) and the same data as bars (front). Green bars have reached their final place.

Sift down

To repair the heap at index i: compare a[i] with its children (2i + 1 and 2i + 2). If the larger child is bigger than a[i], swap them and continue from the child’s position. Each swap moves down one level, so sift-down is O(log n).

Building the heap in O(n)

Leaves are already tiny heaps, so start at the last parent (n/2 − 1) and sift down every node back to the root. Surprisingly, this costs only O(n) in total, because most nodes are near the bottom and sift down only a little.

Code

def sift_down(a, i, size):
    while True:
        l, r = 2 * i + 1, 2 * i + 2
        largest = i
        if l < size and a[l] > a[largest]: largest = l
        if r < size and a[r] > a[largest]: largest = r
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]          # largest to the end
        sift_down(a, 0, end)                 # repair the smaller heap
    return a

print(heap_sort([12, 3, 17, 8, 34, 25, 1]))  # [1, 3, 8, 12, 17, 25, 34]

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

void siftDown(vector<int>& a, int i, int size) {
    while (true) {
        int l = 2 * i + 1, r = l + 1, largest = i;
        if (l < size && a[l] > a[largest]) largest = l;
        if (r < size && a[r] > a[largest]) largest = r;
        if (largest == i) return;
        swap(a[i], a[largest]);
        i = largest;
    }
}

void heapSort(vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
    for (int end = n - 1; end > 0; end--) {
        swap(a[0], a[end]);
        siftDown(a, 0, end);
    }
}

int main() {
    vector<int> a = {12, 3, 17, 8, 34, 25, 1};
    heapSort(a);
    for (int x : a) cout << x << " ";
}

Heap sort vs merge sort vs quick sort

Heap sort’s big strength is the guarantee: O(n log n) time and O(1) space, always. That’s why C++’s std::sort (introsort) falls back to heap sort if quick sort starts going badly.

Common mistakes

• Using a min-heap and expecting ascending order in place (you’d get descending).
• Sifting down with the full size n after shrinking — use the current heap size end.
• Starting build-heap at index n − 1 instead of n/2 − 1 (works, but wastes time on leaves).