Heap sort — in-place, O(n log n)

WHAT is a heap (as an array)?

WHY array, not pointers? A complete tree has no holes — every level is full except possibly the last, filled left-to-right. That regular shape means we can compute child/parent positions with arithmetic, so we need zero pointers and zero extra memory. This is the secret to "in-place".

HOW the algorithm works (two phases)

Phase 1 — Build the heap (heapify the whole array)

Turn an unordered array into a max-heap.

Phase 2 — Sort by repeated extraction

Swap root (max) with last heap slot, shrink heap by one, sift the new root down. Repeat.

The workhorse for both is sift-down (a.k.a. max_heapify).

def sift_down(A, i, n):          # heap occupies A[0..n-1]
    while True:
        l, r = 2*i + 1, 2*i + 2
        largest = i
        if l < n and A[l] > A[largest]: largest = l
        if r < n and A[r] > A[largest]: largest = r
        if largest == i: break        # heap property restored
        A[i], A[largest] = A[largest], A[i]
        i = largest                   # follow the swap downward
 
def heap_sort(A):
    n = len(A)
    # Phase 1: build max-heap, bottom-up from last parent
    for i in range(n//2 - 1, -1, -1):
        sift_down(A, i, n)
    # Phase 2: extract max repeatedly
    for end in range(n - 1, 0, -1):
        A[0], A[end] = A[end], A[0]   # biggest -> sorted tail
        sift_down(A, 0, end)          # restore heap of size `end`

Derivation of the time complexity

Phase 2 is $O(n \log n)$ — easy

We do $n-1$ extractions, each a sift-down on a heap of size $\le n$: $\sum_{k=1}^{n-1} O(\log k) = O(n \log n).$

Phase 1 (build) is $O(n)$ — surprising!

Naive guess: $n$ nodes $\times \log n$ = $O(n\log n)$. Tighter truth: most nodes are near the bottom and sift-down only a little.

At height $h$ from the bottom there are at most $\lceil n / 2^{h+1}\rceil$ nodes, each costing $O(h)$: $T_{\text{build}} = \sum_{h=0}^{\lfloor\log n\rfloor} \frac{n}{2^{h+1}}\,O(h) = O\!\left(n\sum_{h=0}^{\infty}\frac{h}{2^h}\right).$ Now evaluate the series. Let $S=\sum_{h\ge0} h x^h = \dfrac{x}{(1-x)^2}$. At $x=\tfrac12$: $S = \dfrac{1/2}{(1/2)^2} = 2$. Hence $T_{\text{build}} = O(2n) = O(n).$

Worked examples

Common mistakes (steel-manned)

Flashcards

Connections

• Binary Heap — the data structure heap sort runs on.
• Priority Queue — same heap, used for repeated min/max access.
• Quicksort — also in-place but $O(n^2)$ worst case; heap sort guarantees $O(n\log n)$.
• Merge Sort — $O(n\log n)$ and stable, but needs $O(n)$ extra space.
• Complete Binary Tree — why index arithmetic works.
• Big-O Notation — for the build-heap series analysis.
• Introsort — hybrid that falls back to heap sort to dodge quicksort's worst case.

Concept Map

Hinglish (regional understanding)