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

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,13has left child7at index5; no swap.At
i = 1,11exceeds children5and6at indices3and4; no swap.At
i = 0,12has children11and13. Swap indices0and2:[13, 11, 12, 5, 6, 7]. At index2,12exceeds child7, 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.

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 |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 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.

Interview question: write Heap Sort and explain the 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)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 = largestsize 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? |
| 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)-1pass original n after extraction -> sorted suffix re-enters the heap -> pass size=endcompare only the left child -> maximum child may be on the right -> compare both in-range childrenswap 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) - 1down to0.Build-heap is
O(n).The
n - 1extractions make total timeO(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.
Keep learning
Optimal Merge Pattern Interview Questions and Answers: Greedy Proof, Min-Heap Trace and Code
Learn how to explain and implement Optimal Merge Pattern through one exact heap trace, a correctness proof, common traps and ten concise interview answers.
HR Interview Strengths and Weaknesses: Build Answers That Survive Follow-Ups
Turn one truthful project incident into a defensible strength, an honest weakness, and a practice routine that prepares you for probing questions.
DBMS Interview Questions for Freshers: Top 50 with Answers That Survive Follow-Ups
50 DBMS interview questions for freshers, grouped the way interviews actually run: keys, the normalization-to-BCNF-to-denormalization chain, SQL joins, transactions and isolation levels, and indexing, answered as chains so rote definitions become explanations.
Heap Sort MCQs: 10 Solved Questions with Explanations (GATE, ISRO, DSSSB)
Solve 10 heap sort questions drawn from GATE, ISRO, DSSSB and other papers. Each answer explains the tested fact, shortcut or calculation.





