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

Prerequisites worth having open: Binary Heap, Complete Binary Tree, Big-O Notation.

First — the vocabulary these traps assume

Before the traps, let us pin down the words and symbols they lean on, so no line surprises you.

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

Definition Canonical pseudocode (compare the "Spot the error" traps against this)

This is the correct reference. Every trap below is a deviation from one of these lines.

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        # no child bigger -> done
        A[i], A[largest] = A[largest], A[i]
        i = largest                   # follow the swap downward
 
def heap_sort(A):
    n = len(A)
    for i in range(n//2 - 1, -1, -1): # Phase 1: build, bottom-up
        sift_down(A, i, n)
    for end in range(n - 1, 0, -1):   # Phase 2: extract
        A[0], A[end] = A[end], A[0]   # biggest -> sorted tail
        sift_down(A, 0, end)          # heap now size `end`

Recall How Python's

range(start, stop, step) works (read if unsure) range is half-open: it includes start but stops before stop. The step sets direction. So range(n-1, 0, -1) counts down: $n - 1, n - 2, \dots, 1$ — it never reaches 0. And range(n//2-1, -1, -1) counts down to 0 inclusive (it stops before $- 1$ ). This is exactly why the loop bounds in the traps matter: an off-by-one on stop changes which indices are visited.

True or false — justify

A max-heap is a fully sorted array.

False — only the parent ≥ children rule holds, so the root is the max but siblings and cousins are unordered. [6,5,4,1,2,3] is a valid heap yet not sorted.

The right child of a node is always larger than the left child.

False — the heap property only compares parent to child, never child to child. Either child may be larger; nothing links siblings.

Heap sort needs a second array to hold the sorted output.

False — it swaps the max into the array's own tail and shrinks the heap boundary, so the sorted region and heap region share one array. Extra space is

O (1)

Heap sort is a stable sort.

False — sifting swaps elements across long distances, so two equal keys can flip their original order. Use Merge Sort when stability matters.

Building the heap costs

O (n lo g n)

because there are

n

nodes of height up to

lo g n

False — most nodes sit near the bottom and barely sift; the weighted sum

\sum h / 2^{h} = 2

converges, giving

O (n)

. Only the root pays full height.

Heap sort's worst case can degrade to

O (n^{2})

like an unlucky Quicksort.

False — every sift-down is bounded by the tree height

lo g n

regardless of input, so all three cases are

O (n lo g n)

. There is no pathological input.

A complete binary tree can always be packed into an array with no gaps.

True — "complete" means every level is full except possibly the last, filled left-to-right, so index arithmetic (

2 i + 1

2 i + 2

) never lands on a hole.

In Phase 2, after each swap the whole array is re-heapified from scratch.

False — only the new root violates the property (both subtrees are still valid heaps), so a single sift-down of the root suffices, costing

O (lo g n)

not

O (n)

A min-heap will sort an array into ascending order if you park the root at the end.

False — parking the smallest at the back each round produces a descending array. Ascending order needs a max-heap.

The leaves of the heap need to be sift-down'd during Phase 1.

False — a single element is already a valid heap, so all indices past

⌊ n /2 ⌋ - 1

are skipped. Only internal nodes get sifted.

Spot the error

sift_down(A, 0, len(A)) inside the Phase-2 extraction loop.

The size argument must be the shrinking end, not len(A). Passing the full length lets sift-down reach into the already-sorted tail and drag parked maxima back into the heap.

Phase 1 loop written as for i in range(0, n//2) (top-down).

Wrong direction — top-down violates sift-down's precondition, because a node's subtrees aren't heaps yet when you process it. You must go bottom-up (range(n//2-1, -1, -1)) so children are fixed first.

In sift-down, comparing only A[l] to A[i] and swapping if larger, ignoring A[r].

You must pick the larger of both children before swapping. Swapping with the left child when the right is bigger can put a smaller value on top, breaking the heap property below.

Phase 2 loop written for end in range(n-1, -1, -1).

The lower bound is off by one — since range stops before its stop value, -1 makes end reach 0, doing a useless swap of one element with itself. The correct bound is range(n-1, 0, -1), which stops at 1.

After swapping root with a child, the code stops instead of continuing down.

One swap can break the heap property one level lower, so sift-down must follow the swapped path downward (i = largest) until no child is larger. Stopping early leaves a violation deeper in the tree.

Using parent = i//2 for a 0-based array.

That formula is for 1-based heaps. In 0-based indexing the parent is

⌊(i - 1) /2 ⌋

; using i//2 points to the wrong node and corrupts the structure.

Claiming "the recursion in sift-down makes heap sort

O (lo g n)

space."

The recursion depth is

lo g n

, but the standard implementation rewrites it as a loop, making extra space

O (1)

. Only the naive recursive version would use

O (lo g n)

stack.

Why questions

Why is the maximum always at index 0 in a max-heap?

Because every parent is ≥ both children transitively up the tree, so no element can exceed the root. The root dominates every path to it.

Why does heap sort avoid the extra

O (n)

memory that Merge Sort needs?

The heap lives inside the input array via index arithmetic, and extraction parks maxima in the same array's tail — nothing is copied to a side buffer.

Why is the build phase done bottom-up rather than top-down?

Sift-down assumes both subtrees are already valid heaps. Processing from the last internal node upward guarantees this precondition holds at every step.

Why is sift-down bounded by the tree height and not the node count?

It walks a single root-to-leaf path, doing

O (1)

work per level, so its cost is the number of levels it can descend — the height,

⌊ lo g_{2} n ⌋

Why does the series

\sum_{h \geq 0} h / 2^{h}

matter for the build cost?

It weights each height

h

by how many nodes sit there (

n / 2^{h + 1}

) times the work (

h

). Since the sum converges to 2, the total build cost collapses to

O (n)

Why can heap sort use a loop instead of recursion for sift-down?

Sift-down is tail-recursive — the recursive call is the last action with no pending work after it, so it converts directly to a while loop, saving stack space.

Why does a Priority Queue use the same heap but never runs Phase 2?

A priority queue interleaves inserts and single extract-max/min operations over time, whereas heap sort extracts all elements at once; the underlying sift-down machinery is identical.

Edge cases

What does heap sort do with an empty array?

Both loops have empty ranges (n//2-1 = -1, range(-1,-1,-1) and range(-1,0,-1) are empty), so it does nothing and correctly returns the empty array.

What happens on a single-element array?

Phase 1 skips (the one node is a leaf, already a heap) and Phase 2's range(0,0,-1) is empty, so the element is trivially sorted with zero swaps.

What if all elements are equal, e.g. [5,5,5,5]?

Every comparison finds no strictly larger child, so sift-down stops immediately and no swaps occur; the array is already sorted (stability is moot since keys are identical).

An already-sorted ascending array — is heap sort faster?

No — heap sort ignores existing order; it still builds the heap in

O (n)

and extracts in

O (n lo g n)

. There is no "best case" shortcut, unlike insertion sort.

A node has a left child but the right-child index falls outside the heap.

The guard r < n prevents reading past the boundary, so sift-down considers only the existing left child. This is why the bounds check appears before every comparison.

An odd-length array — does the last parent have one or two children?

The last internal node may have only a left child if the last level ends on an odd index; the l < n / r < n guards handle exactly this asymmetry.

Flashcards

Does heap sort have a favourable best case on sorted input?

No — it always builds and fully extracts, so best = average = worst =

O (n lo g n)

Why must Phase 2 pass a shrinking size to sift-down?

So sift-down never reaches into the already-sorted tail and drags parked maxima back into the heap.

Which sort is heap sort's stable alternative?

Merge sort, which preserves the order of equal keys.

What precondition makes bottom-up build correct?

When a node is sifted, both its subtrees are already valid heaps.

How do you derive the last internal-node index?

Largest

i

with

2 i + 1 < n

, giving

i = ⌊ n /2 ⌋ - 1

Recall Fastest sanity check for any "heap sort is stable/fast/needs-memory" claim

Three anchors settle almost every trap: it's not stable (swaps reorder equals), it's $O (1)$ extra space (in-place via index math), and it's $O (n lo g n)$ in all cases (height-bounded sift-down). If a claim contradicts one of these, it's the trap.

Connections

Parent: Heap sort — the full derivation these traps probe.
Binary Heap — the structure whose invariants half these traps test.
Complete Binary Tree — why array packing has no holes.
Big-O Notation — the language of the build-cost argument.
Quicksort · Merge Sort · Introsort — contrast points for stability and worst case.