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