Heap Sort Interview Questions and Answers: Trace, Code, and Follow-Ups

Learn to build a max-heap, trace every extraction, explain iterative sift-down, justify the time and space bounds, and handle common Heap Sort follow-ups.

KnowledgeGate Team

Exam prep & CS education

Updated 2 Nov 20265 min read
Heap Sort Interview Questions and Answers: Trace, Code, and Follow-Ups

Candidates may know O(n log n) yet struggle to build the heap, explain its shrinking boundary, or prove build-heap is O(n). The key interview moves are building the heap, tracing its shrinking boundary, proving build-heap is O(n), and debugging sift-down on [12, 11, 13, 5, 6, 7]. See Coding & Skills for broader learning.

What is Heap Sort? Give the 30-second interview answer

“What is Heap Sort, and how does it work?”

Heap Sort is an in-place comparison sort. It builds a heap, then repeatedly moves the root to the unsorted range's final position. For ascending order, use a max-heap: swap index 0 with the active heap's last element, shrink the heap, and restore its property.

In a zero-based array, index i has left child 2i + 1, right child 2i + 2, and parent floor((i - 1) / 2) when i > 0. For length n, the last non-leaf is floor(n/2) - 1.

The headline answers: O(n log n) best, average, and worst-case time; O(1) auxiliary space with iterative heapify; and no stability in-place.

Interview question: build the max-heap by hand

For a = [12, 11, 13, 5, 6, 7], n = 6. Construction starts at floor(6/2) - 1 = 2, visiting 2, 1, 0.

  • At i = 2, 13 has left child 7 at index 5; no swap.

  • At i = 1, 11 exceeds children 5 and 6 at indices 3 and 4; no swap.

  • At i = 0, 12 has children 11 and 13. Swap indices 0 and 2: [13, 11, 12, 5, 6, 7]. At index 2, 12 exceeds child 7, so heapify stops.

The invariant: after processing i, its subtree is a max-heap. After index 0, the active range is a max-heap. Leaves need no calls because each is already a one-node heap. For more on heap shape and heapify, read Binary Heaps for GATE.

Two panels show the array and tree before and after bottom-up max-heap construction, with checks at indices 2, 1 and 0.

Interview question: trace every extraction pass

Continue from [13, 11, 12, 5, 6, 7]. Here, end becomes the exclusive heap size after the root swap.

Pass

After root swap

After heapify

end=5

[7, 11, 12, 5, 6, 13]

[12, 11, 7, 5, 6, 13]

end=4

[6, 11, 7, 5, 12, 13]

[11, 6, 7, 5, 12, 13]

end=3

[5, 6, 7, 11, 12, 13]

[7, 6, 5, 11, 12, 13]

end=2

[5, 6, 7, 11, 12, 13]

[6, 5, 7, 11, 12, 13]

end=1

[5, 6, 7, 11, 12, 13]

No heapify needed

After each heapify, a[0..end-1] is a max-heap and a[end..n-1] a final ascending suffix whose values are at least those remaining. With root-to-end swaps, a max-heap produces ascending order and a min-heap descending order.

Six array rows show Heap Sort shrinking the active max-heap and growing the final ascending suffix from the worked values.

Interview question: write Heap Sort and explain the code

Code
heapSort(a):
    n = length(a)
    for start = floor(n / 2) - 1 downto 0:
        siftDown(a, start, n)
    for end = n - 1 downto 1:
        swap(a[0], a[end])
        siftDown(a, 0, end)
Code
siftDown(a, root, size):
    while true:
        left = 2 * root + 1
        if left >= size:
            return
        largest = left
        right = left + 1
        if right < size and a[right] > a[left]:
            largest = right
        if a[root] >= a[largest]:
            return
        swap(a[root], a[largest])
        root = largest

size is exclusive, so passing end excludes the fixed suffix. Narrate two phases: build the max-heap, then preserve the shrinking-heap invariant. Empty and one-element arrays are no-ops; duplicates and negatives need no special logic. Either equal child may be selected, but Heap Sort does not preserve equal-key order.

Why is Heap Sort O(n log n) if build-heap is O(n)?

Bottom-up build-heap is O(n) because most nodes lie near leaves and travel little. At most n/2^(h+1) nodes have height h, each costing O(h). Thus work is bounded by:

n * sum(h / 2^(h+1)) = O(n)

Do not charge every node log n. Sorting performs n - 1 extractions, each restoring through at most floor(log2 n) levels. Therefore O(n) + O(n log n) = O(n log n) in all cases.

The iterative array version uses O(1) auxiliary space. Recursive heapify can add up to O(log n) call-stack space.

Is Heap Sort stable, in-place, adaptive, or preferable to Quicksort?

Question

Model answer

Reason

Stable?

No

Long-distance swaps can reverse equal keys

In-place?

Yes, with iterative heapify

It rearranges the input and uses constant extra state

Adaptive?

No

Sorted input still goes through construction and extraction

Worst-case bound?

O(n log n)

Heap height bounds every restoration

For a stability counterexample, label identities. From [2a, 2b, 1], an implementation that avoids swapping equal keys can produce [1, 2b, 2a]. Equal keys 2a and 2b reversed, proving instability.

Heap Sort offers deterministic O(n log n) worst-case time and constant auxiliary array space. Quicksort often wins on locality and constants, but its worst case depends on pivots. Merge Sort is stable and O(n log n), but arrays usually require O(n) auxiliary space. See Sorting Algorithms: Complexity, Stability, n log n Bound.

How interviews test Heap Sort, and the traps that lose marks

A typical ladder: define the algorithm, build a heap, trace an extraction, write sift-down, justify build-heap O(n), then discuss stability and alternatives. No universal interview syllabus or fixed frequency exists.

Use this exact mistake -> failure -> repair checklist:

  • start build at n-1 -> wasted leaf calls and confused reasoning -> start at floor(n/2)-1

  • pass original n after extraction -> sorted suffix re-enters the heap -> pass size=end

  • compare only the left child -> maximum child may be on the right -> compare both in-range children

  • swap once and return -> a lower violation can remain -> continue from the child's new index

Check these boundaries aloud: [] -> [], [8] -> [8], [2, 1] -> [1, 2], [3, 3, 1] -> [1, 3, 3], [1, 2, 3, 4] -> [1, 2, 3, 4], [4, 3, 2, 1] -> [1, 2, 3, 4], and [0, -2, 5, -1] -> [-2, -1, 0, 5].

The short version and the next practice step

  • Ascending order uses a max-heap.

  • Build from floor(n/2) - 1 down to 0.

  • Build-heap is O(n).

  • The n - 1 extractions make total time O(n log n).

  • Iterative heapify gives O(1) auxiliary space.

  • Ordinary Heap Sort is not stable.

Final whiteboard check: build a max-heap from [4, 10, 3, 5, 1]. Process indices 1, then 0, yielding [10, 5, 3, 4, 1]: 10 exceeds 5 and 3, while 5 exceeds 4 and 1.

Choose your next route: DSA using Java for structured implementation, Coding for Placements for wider preparation, or the Coding & Skills category above for the broader catalog.