## Convert A Min Heap To Max Heap

Difficulty: Medium

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

#### 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 bottom-most and rightmost internal node of min Heap and then heapify all internal modes in the bottom-up way to build the Max heap.

Why this method will work?

To build a heap, the following algorithm is implemented for any input array.

``````BUILD-HEAP(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 Build-Heap makes ``` n ``` such calls. This upper bound, though correct, is not asymptotically tight. In reality, building a heap takes ``` O(n) ``` time depending on the implementation.

There may be two different ways to implement ``` BUILD-HEAP ```

1. Start at the top of the heap (the beginning of the array) and call ``` shiftUp ``` on each item. At each step, the previously sifted items (the items before the current item in the array) form a valid heap and sifting the next item up places it into a valid position in the heap. After sifting up each node, all items satisfy the heap property.
2. 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 ``` shiftDown ``` and ``` shiftUp ``` is:

• ``` shiftDown ``` swaps a node that is too small with its largest child (thereby moving it down) until it is at least as large as both nodes below it.
• ``` shiftUp ``` swaps a node that is too large with its parent (thereby moving it up) until it is no larger than the node above it.

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 ``` n/2 ``` elements go on the bottom row of the heap. ``` h=0 ``` , so heapify is not needed.

( Step 2 ) The next ``` n/2² ``` elements go on row 1 up from the bottom. ``` h=1 ``` , heapify filters 1 level down.

( Step i ) The next ``` n/(2^i) ``` elements go in row ``` i ``` up from the bottom. ``` h=i ``` , heapify filters ``` i ``` levels down.

( Step log(n) ) The last ``` n/(2^log2(n)) = 1 ``` element goes in row ``` log(n) ``` up from the bottom. ``` h=log(n) ``` , heapify filters ``` log(n) ``` levels down.

Note: After step one, ``` 1/2 ``` of the elements ``` (n/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 ``` log(n) ``` complexity.

Theoretically

The Total steps ``` N ``` to build a heap of size ``` n ``` can be written out mathematically.

At height ``` i ``` , we've shown (above) that there will be ``` n/(2^i+1) ``` elements that need to call heapify, and we know heapify at height ``` i ``` is ``` O(i) ``` . This gives:

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 ``` x = 1/2 ``` into the above equation yields ``` 2 ``` . Plugging this into the first equation gives:

Thus, the total number of steps is of size ``` O(n) ```

Solution steps

1. Convert the given array of elements into an almost complete binary tree.
2. Ensure that the tree is a max heap.
• Check that every non-leaf 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 non-leaf 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 = (n-2)/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 min-heap 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 min-heap
• 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!