DSA interview question

Heap Fundamentals: Heap Sort In Place

Easy · Data structures · Topics: heap, theory

The problem

An embedded device must sort sensor readings in place with guaranteed O(n log n) time and O(1) extra memory. Quicksort's worst case and merge sort's buffer are both unacceptable. Heap sort meets all three, and building it exercises every heap fundamental:

the array layout of a complete binary tree (children of i at 2i + 1 and 2i + 2)
sift-down
bottom-up heapify in O(n)
repeatedly moving the maximum to the end of the array

Example: [5, 2, 9, 1, 5, 6] → [1, 2, 5, 5, 6, 9].

Function signature

void heapSort(vector<int>& a);  // ascending, in place

Test cases

Input	Output	Explanation
`[5, 2, 9, 1, 5, 6]`	`[1, 2, 5, 5, 6, 9]`	Duplicates are fine
`[3, 2, 1]`	`[1, 2, 3]`
`[-1, -3, 2, 0]`	`[-3, -1, 0, 2]`
`[7]`	`[7]`
`[]`	`[]`

(Confirm: in-place, O(1) extra memory; stability isn't required, and heap sort isn't stable.)

How interviewers phrase it

"Explain how a binary heap works and use it to sort an array in place."
It usually leads into priority-queue problems (k-th largest, merge k lists, median of a stream).

Clarifying questions to ask

Ascending or descending? (Ascending uses a max-heap.)
Is O(1) extra memory required? (Yes, which is the point of heap sort.)
Does stability matter? (Heap sort isn't stable.)

Follow-ups to expect

"How is a heap stored in an array?"
"What's the heap property?"
"Why is building a heap O(n), not O(n log n)?"
"sift-up vs sift-down?"
"Complexity of heap sort?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview