Heap Sort takes Selection Sort’s idea — repeatedly pick the maximum remaining element — and makes the “pick” fast by storing the array as a binary max-heap. Extracting the maximum costs O(log n) instead of a full scan.

The result: a guaranteed O(n log n) sort that is fully in-place with no recursion. Reach for it when you need a hard worst-case bound and O(1) extra space.

How It Works

1. Build a max-heap: rearrange the array so every parent is ≥ its children (the root is the maximum). This is done bottom-up with heapify.
2. Extract the max: swap the root with the last element of the heap, shrinking the heap size by one.
3. Sift down: restore the heap property at the new root.
4. Repeat steps 2–3 until the heap is empty — the tail of the array is now the sorted output.

Key Insight

The heap is stored implicitly in a flat array: index i has children 2i+1 and 2i+2, and parent ⌊(i-1)/2⌋. No pointers — the “tree” is just the array indices.

The clever part: building the heap costs O(n), not O(n log n). heapify on a node of height h costs O(h), and there are exponentially more short nodes than tall ones — which sums to linear. The extraction phase then costs O(n log n): n extractions × O(log n) sift-downs.

Worked Example

Sort [5, 3, 8, 1, 2] with Heap Sort:

1. Build max-heap (bottom-up): sift index 1 (3) and index 0 (5) to produce [8, 3, 5, 1, 2] → then [8, 5, 3, 1, 2].
2. Extract 8: swap with last → [2, 5, 3, 1, | 8], sift → [5, 2, 3, 1, | 8].
3. Extract 5: swap → [1, 2, 3, | 5, 8], sift → [3, 2, 1, | 5, 8].
4. Extract 3: swap → [1, 2, | 3, 5, 8], sift → [2, 1, | 3, 5, 8].
5. Extract 2: swap → [1, | 2, 3, 5, 8], done.

Result: [1, 2, 3, 5, 8]. The vertical bar shows the sorted region growing from the right while the heap shrinks from the left.

Edge Cases & Pitfalls

• Duplicates — Heap Sort is unstable: the extract-max swap can reorder equal values unpredictably.
• All identical values — still O(n log n): the heap is trivially valid, but every extraction runs a full sift-down.
• Cache locality — parent/child indices are far apart, so the heap has poor cache behavior versus quicksort. Usually slower in practice despite the same asymptotics.
• Build-heap off-by-one — only sift internal nodes from index ⌊n/2⌋−1 down to 0; sifting leaves is wasted work (but harmless).

Comparison With Other Sorts

Applications

• Priority-queue-based scheduling (the extract-max loop is exactly how a priority queue works)
• Embedded/real-time contexts needing a guaranteed worst case with no recursion
• Selection problems: heap’s extract-max can find the k largest elements in O(n + k log n)

Practice Trajectory

1. Draw the array [7, 3, 9, 1, 4, 8, 2] as a heap tree using the 2i+1/2i+2 index rule.
2. Hand-trace heapify on the root after one extraction.
3. Explain why build-heap is O(n) — sum the per-level costs.
4. Trace the full sort of [4, 10, 3, 5, 1], marking the sorted region after each extraction.
5. Implement heap sort and verify it never uses more than O(1) auxiliary space.