Convert A Min Heap To Max Heap
Difficulty: Medium
Asked in: Google
Understanding The Problem
Problem Description
Given array representation of min Heap , write a program to convert it to max Heap . The expected time complexity is O(n).
Example
Input: A[] = [3 5 9 6 8 20 10 12 18 9]
3
/ \
5 9
/ \ / \
6 8 20 10
/ \ /
12 18 9
Output: A[] = [20 18 10 12 9 9 3 5 6 8] or any Max Heap formed from input elements
20
/ \
18 10
/ \ / \
12 9 9 3
/ \ /
5 6 8
You may attempt the problem here.
You should read about the introduction of heaps from here .
Solution
Our final goal is to only build the max heap and the problem expects the solution to be in
O(n)
time complexity. The idea is very simple, we simply build Max Heap without caring about the input.
We start from the bottommost and rightmost internal node of min Heap and then heapify all internal modes in the bottomup way to build the Max heap.
Why this method will work?
To build a heap, the following algorithm is implemented for any input array.
BUILDHEAP(A)
heapsize := size(A)
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i)
end for
END
A quick look over the above algorithm suggests that the running time is
O(n log n)
since each call to
heapify
costs
O(log n)
and
BuildHeap
makes
such calls. This upper bound, though correct, is not asymptotically tight. In reality, building a heap takes
n
O(n)
time depending on the implementation.
There may be two different ways to implement
BUILDHEAP

Start at the top of the heap (the beginning of the array) and call
shiftUp
 Or, go in the opposite direction: start at the end of the array and move back towards the front. At each iteration, you shift an item down until it is in the correct location.
Where
and
shiftDown
is:
shiftUp

shiftDown

shiftUp
The logic does not produce a tight bound — it overestimates the complexity of each heapify. If built from the bottom up, insertion (heapify) can be much less than
O(log(n))
.
The process is as follows:
( Step 1 )
The first
elements go on the bottom row of the heap.
n/2
, so heapify is not needed.
h=0
( Step 2 )
The next
elements go on row 1 up from the bottom.
n/2²
, heapify filters 1 level down.
h=1
( Step i )
The next
elements go in row
n/(2^i)
up from the bottom.
i
, heapify filters
h=i
levels down.
i
( Step
log(n)
)
The last
element goes in row
n/(2^log2(n)) = 1
up from the bottom.
log(n)
, heapify filters
h=log(n)
levels down.
log(n)
Note:
After step one,
of the elements
1/2
are already in the heap, and we didn't even need to call heapify once. Also, notice that only a single element, the root, actually incurs the full
(n/2)
complexity.
log(n)
Theoretically
The Total steps
N
to build a heap of size
can be written out mathematically.
n
At height
, we've shown (above) that there will be
i
elements that need to call heapify, and we know heapify at height
n/(2^i+1)
i
is
. This gives:
O(i)
The solution to the last summation can be found by taking the derivative of both sides of the well known geometric series equation:
Finally, plugging in
into the above equation yields
x = 1/2
2
. Plugging this into the first equation gives:
Thus, the total number of steps is of size
O(n)
Solution steps
 Convert the given array of elements into an almost complete binary tree.
 Ensure that the tree is a max heap.
 Check that every nonleaf node contains a greater or equal value element than its child nodes.
 If there exists any node that does not satisfy the ordering property of max heap, swap the elements.
 Start checking from a nonleaf node with the highest index (bottom to top and right to left).
Pseudo Code
void MaxHeapify(int arr[], int i, int n)
{
left = 2*i + 1
right = 2*i + 2
largest = i
if (left < n and arr[left] > arr[i])
largest = left
if (right < n and arr[right] > arr[largest])
largest = right
if (largest != i)
{
swap(arr[i], arr[largest])
MaxHeapify(arr, largest, n)
}
}
void convertMaxHeap(int arr[], int n)
{
// Start from bottommost and rightmost
// internal mode and heapify all internal
// modes in bottom up way
for (int i = (n2)/2 to i >= 0)
MaxHeapify(arr, i, n)
}
Complexity Analysis
Time Complexity: O(n) (How?)
Space Complexity: O(log n), because of the stack space required for recursion.
Critical Ideas to Think
 How building max heap uses O(n) time complexity instead of O(n log n)? Can you prove it mathematically?
 Does the input array being a minheap instead of randomly filled values affect the time complexity in the above approach?
 If the input array is a max heap and the required output is a Min heap, Will the above approach will work? If yes, Why?
Suggested Problems To Solve
 Maximum distinct elements after removing k elements
 Height of a complete binary tree (or Heap) with N nodes
 Heap Sort for decreasing order using minheap
 Print all nodes less than a value x in a Min Heap.
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!