DSA interview question

Convert a Min Heap to a Max Heap

Medium · Data structures · Topics: heap

The problem

A game server stores player scores in a min-heap (to evict the lowest score quickly), but a new leaderboard feature needs a max-heap of the same scores, built in place and fast. The min-heap order doesn't help, so treat the array as arbitrary and run bottom-up heapify for a max-heap: sift down every internal node from the last one to the root. That costs O(n), not O(n log n) as n separate insertions would.

Example: [3, 5, 9, 6, 8, 20, 10, 12, 18, 9] → [20, 18, 10, 12, 9, 9, 3, 5, 6, 8].

Function signature

void convertMinToMaxHeap(vector<int>& a);  // in place

Test cases

Input (a min-heap)	Output (a max-heap)	Explanation
`[3, 5, 9, 6, 8, 20, 10, 12, 18, 9]`	`[20, 18, 10, 12, 9, 9, 3, 5, 6, 8]`
`[1, 2, 3]`	`[3, 2, 1]`
`[1, 2, 3, 4]`	`[4, 2, 3, 1]`
`[5, 5]`	`[5, 5]`
`[10]`	`[10]`

(Confirm: any valid max-heap arrangement is acceptable; the outputs shown are what bottom-up heapify produces.)

How interviewers phrase it

"Given an array representing a min heap, convert it into a max heap" (GeeksforGeeks "Convert min Heap to max Heap").

Clarifying questions to ask

In place? (Yes.)
Is any valid max-heap acceptable? (Usually yes.)
Expected time? (O(n).)

Follow-ups to expect

"Does the min-heap structure help?"
"Why start at n/2 − 1?"
"Why is it O(n)?"
"Recursive vs iterative sift-down?"
"Could you insert elements one by one instead?"

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