Convert Min Heap to Max Heap
MediumHeapify from the last internal node backwards
Problem
Given an array that is a min-heap, rearrange it into a max-heap.
Run heapify for a max-heap: sift each node down starting from the last parent, in O(n).
The idea
A min-heap tells you nothing useful about max-heap order, so rebuild it: sift down every internal node starting from the last one and working towards the root. Bottom-up heapify is O(n), better than inserting each element into a fresh heap.
The trick
- Start at index n/2 - 1 and walk down to 0.
- O(n) overall — most nodes are near the leaves and barely move.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [3,5,9,6,8,20,10,12,18,9] Values: 3, 5, 9, 6, 8, 20, 10, 12, 18, 9.
1for i from n/2-1 down to 0: maxHeapify(i)Input
- array
- [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
- Output:
- a valid max-heap
- Explanation:
- Re-heapify so every parent >= its children.
Example 2
- Input:
- nums = [1, 2, 3]
- Output:
- [3,1,2] (one valid max-heap)
- Explanation:
- Sift down from the last parent.
Example 3
- Input:
- nums = [5]
- Output:
- [5]
- Explanation:
- A single element is already a heap.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.