Heap SortHeapsort

01Why it exists

Reach for it when you see:Sort in place, O(1) extra space, O(n log n) even in the worst case, no recursion allowed, fear of adversarial input hitting the worst case, a fallback for quicksort, pulling out the largest few as you go.

02The core idea

Heap sort is selection sort with a better tool. Selection sort has to scan the whole unsorted region to find its extreme value, which costs O(n); but if that region is itself a max-heap, the maximum is already sitting at a[0] and repairing the heap after you take it costs only O(log n). The algorithm runs in two phases, both entirely inside the original array. heapify: turn the whole array into a max-heap. Extract: repeatedly swap the root a[0] with the last slot of the heap, shrink the heap by one, and sift down the new root. The array is therefore split in two: [0, size) is the heap, [size, n) is the sorted tail, and the tail grows by one slot each round.

Correctness rests on an invariant: at the start of every round, a[size..n−1] holds the n − size largest elements in ascending order, and a[0..size−1] is a max-heap of everything else. The root is the largest element in the heap and no larger than anything in the tail, so swapping it to size − 1 leaves the tail sorted and one slot longer. The element that lands at the root breaks the heap property in exactly one place — both subtrees are still heaps — so a single sift down repairs it and the invariant carries into the next round; once size drops to 1 the whole array is sorted. Building the heap works the same way: everything from index n // 2 on is a leaf and therefore already a heap, so processing backwards from n // 2 − 1 means that by the time node i comes up its two subtrees are heaps, and one sift down makes the subtree rooted at i a heap too.

Complexity: heapify looks like n/2 sift downs at O(log n) each, but there are at most ⌈n / 2^(h+1)⌉ nodes of height h and each sinks at most h levels, so the total is Σ h · n / 2^(h+1) = O(n) — most nodes sit near the bottom and barely sink at all. The extraction phase performs n − 1 sift downs, each walking at most the tree height of ⌊log₂ n⌋ levels, giving O(n log n). There is no unlucky input: sorted, reversed or random, the best, average and worst cases are all O(n log n) (a degenerate case like all-equal elements is actually O(n), because every sift down stops on its first step). With sift down written as a loop the extra space is O(1); written recursively it needs an O(log n) call stack, which no longer counts as truly in place.

Three mistakes come up again and again. Sift down must test child existence against size, the current heap size, not n, or the sorted tail gets pulled back into the heap. The build loop has to run backwards from n // 2 − 1; forwards, the subtrees are not heaps yet. And ascending order needs a max-heap — an in-place min-heap sorts descending. Heap sort is also not stable: [2a, 2b, 1] comes out as [1, 2b, 2a], with the two 2s in the wrong relative order. Against its neighbours: merge sort is stable but needs O(n) of scratch space; quicksort is faster on average because partitioning sweeps sequentially through adjacent memory, whereas sift down jumps from i to 2i + 1, which on a large array means a cache miss at nearly every step. That is why heap sort is rarely the workhorse — it shows up when you cannot afford extra memory and cannot accept an O(n²) worst case. Binary Heap covers the heap itself, Top-K uses a heap of size K, and here the whole array is turned into a heap in place.

03The algorithm

1. 1Write sift_down(a, i, size): find the largest of i, 2i + 1 and 2i + 2, where a child index only exists if it is < size. If the largest is i, stop; otherwise swap, move i to that child, and repeat.
2. 2Build the heap: run i from n // 2 − 1 down to 0, calling sift_down(a, i, n) for each. When that finishes, a[0] holds the maximum.
3. 3Extract: run end from n − 1 down to 1, swapping a[0] with a[end]. This round's maximum lands at end and never moves again.
4. 4Call sift_down(a, 0, end) on the new root. The heap is now end slots long — passing n would drag the already-sorted tail back in.
5. 5When the loop ends the array is sorted ascending. For descending order, flip the comparison (a min-heap); for just the k largest, stop after k extractions, which costs O(n + k log n).

04Interactive demo

Both views share the array [5, 2, 9, 1, 7, 3, 8, 4]. The tree on top draws only the part still inside the heap, and the [i] under each node is its array index; below is that same array, with the sorted tail in green. Yellow marks the parent and child currently being compared, blue the two slots just swapped. Steps 1 through 8 are the heapify, which ends at [9, 7, 8, 4, 2, 3, 5, 1]; after that, every extraction is a single swap of the root with the tail followed by sinking the new root, and that sink never goes deeper than the height of the tree.

05Code

The heart of it is a hand-written sift_down plus the two-phase heap_sort. Python adds a generator built on heapq that emits results as you go, matching the paginated results scenario: it is not in place, but it shows the O(n + k log n) cost of taking only the first k. C++ rewrites the same algorithm with the standard library's std::make_heap and std::pop_heap, where passing std::greater flips it to descending order.

import heapq
from itertools import islice


def sift_down(a, i, size):
    """Sink a[i] until it is no smaller than both children. Only the first size slots count."""
    while True:
        l, r, largest = 2 * i + 1, 2 * i + 2, i
        if l < size and a[l] > a[largest]:     # compare against size, not len(a)
            largest = l
        if r < size and a[r] > a[largest]:
            largest = r
        if largest == i:                       # the max-heap property holds
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest


# Heap sort: in place, O(1) extra space, O(n log n) worst case, not stable
def heap_sort(a):
    n = len(a)
    # Phase 1: heapify. Everything from index n // 2 on is a leaf, so start at the last internal node
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    # Phase 2: the root is the maximum. Swap it to the end, shrink the heap, then repair the root
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)                   # only the first end slots; the tail is already sorted
    return a


# Variation: emit as you go (not in place). O(n) to build, then O(log n) per item
# Taking only the first k costs O(n + k log n); taking them all is one full heap sort
def iter_largest(nums):
    h = [-x for x in nums]                     # heapq is a min-heap, so negate to get a max-heap
    heapq.heapify(h)
    while h:
        yield -heapq.heappop(h)


if __name__ == "__main__":
    print(heap_sort([5, 2, 9, 1, 7, 3, 8, 4]))     # [1, 2, 3, 4, 5, 7, 8, 9]
    scores = [62, 95, 71, 88, 95, 40, 79]
    print(list(islice(iter_largest(scores), 3)))   # [95, 95, 88] (page one needs only the top 3)

06Practice

• LeetCode 506Relative Ranks (pop from a max-heap in order; the nth item out is the nth rank)Easy
• LeetCode 1636Sort Array by Increasing Frequency (change what sift_down compares: frequency first, larger value first on ties)Easy
• LeetCode 912Sort an Array (write heap sort by hand: O(1) extra space and O(n log n) worst case)Medium
• LeetCode 215Kth Largest Element in an Array (heapify, then extract only k times — heap sort stopped early)Medium
• LeetCode 1962Remove Stones to Minimize the Total (heapify in place, then repeatedly edit the root and sink it)Medium