# Convert min Heap to max Heap

Given array representation of min Heap, convert it to max Heap in O(n) time.
Example :

```Input: arr[] = [3 5 9 6 8 20 10 12 18 9]
3
/
5       9
/       /
6     8  20   10
/     /
12   18 9

Output: arr[] = [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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The problem might look complex at first look. But our final goal is to only build the max heap. The idea is very simple – we simply build Max Heap without caring about the input. We start from bottom-most and rightmost internal mode of min Heap and heapify all internal modes in bottom up way to build the Max heap.

Below is its implementation

## C++

 `// A C++ program to convert min Heap to max Heap ` `#include ` `using` `namespace` `std; ` ` `  `// to heapify a subtree with root at given index ` `void` `MaxHeapify(``int` `arr[], ``int` `i, ``int` `n) ` `{ ` `    ``int` `l = 2*i + 1; ` `    ``int` `r = 2*i + 2; ` `    ``int` `largest = i; ` `    ``if` `(l < n && arr[l] > arr[i]) ` `        ``largest = l; ` `    ``if` `(r < n && arr[r] > arr[largest]) ` `        ``largest = r; ` `    ``if` `(largest != i) ` `    ``{ ` `        ``swap(arr[i], arr[largest]); ` `        ``MaxHeapify(arr, largest, n); ` `    ``} ` `} ` ` `  `// This function basically builds max heap ` `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; i >= 0; --i) ` `        ``MaxHeapify(arr, i, n); ` `} ` ` `  `// A utility function to print a given array ` `// of given size ` `void` `printArray(``int``* arr, ``int` `size) ` `{ ` `    ``for` `(``int` `i = 0; i < size; ++i) ` `        ``printf``(``"%d "``, arr[i]); ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``// array representing Min Heap ` `    ``int` `arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` ` `  `    ``printf``(``"Min Heap array : "``); ` `    ``printArray(arr, n); ` ` `  `    ``convertMaxHeap(arr, n); ` ` `  `    ``printf``(````" Max Heap array : "````); ` `    ``printArray(arr, n); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to convert min Heap to max Heap ` ` `  `class` `GFG  ` `{ ` `    ``// To heapify a subtree with root at given index ` `    ``static` `void` `MaxHeapify(``int` `arr[], ``int` `i, ``int` `n) ` `    ``{ ` `        ``int` `l = ``2``*i + ``1``; ` `        ``int` `r = ``2``*i + ``2``; ` `        ``int` `largest = i; ` `        ``if` `(l < n && arr[l] > arr[i]) ` `            ``largest = l; ` `        ``if` `(r < n && arr[r] > arr[largest]) ` `            ``largest = r; ` `        ``if` `(largest != i) ` `        ``{ ` `            ``// swap arr[i] and arr[largest] ` `            ``int` `temp = arr[i]; ` `            ``arr[i] = arr[largest]; ` `            ``arr[largest] = temp; ` `            ``MaxHeapify(arr, largest, n); ` `        ``} ` `    ``} ` `  `  `    ``// This function basically builds max heap ` `    ``static` `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``; i >= ``0``; --i) ` `            ``MaxHeapify(arr, i, n); ` `    ``} ` `  `  `    ``// A utility function to print a given array ` `    ``// of given size ` `    ``static` `void` `printArray(``int` `arr[], ``int` `size) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < size; ++i) ` `            ``System.out.print(arr[i]+``" "``); ` `    ``} ` `     `  `    ``// driver program ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``// array representing Min Heap ` `        ``int` `arr[] = {``3``, ``5``, ``9``, ``6``, ``8``, ``20``, ``10``, ``12``, ``18``, ``9``}; ` `        ``int` `n = arr.length; ` `  `  `        ``System.out.print(``"Min Heap array : "``); ` `        ``printArray(arr, n); ` `  `  `        ``convertMaxHeap(arr, n); ` `  `  `        ``System.out.print(````" Max Heap array : "````); ` `        ``printArray(arr, n); ` `    ``} ` `} ` ` `  `// Contributed by Pramod Kumar `

## Python3

 `# A Python3 program to convert min Heap ` `# to max Heap  ` ` `  `# to heapify a subtree with root  ` `# at given index  ` `def` `MaxHeapify(arr, i, n): ` `    ``l ``=` `2` `*` `i ``+` `1` `    ``r ``=` `2` `*` `i ``+` `2` `    ``largest ``=` `i  ` `    ``if` `l < n ``and` `arr[l] > arr[i]:  ` `        ``largest ``=` `l ` `    ``if` `r < n ``and` `arr[r] > arr[largest]:  ` `        ``largest ``=` `r  ` `    ``if` `largest !``=` `i: ` `        ``arr[i], arr[largest] ``=` `arr[largest], arr[i]  ` `        ``MaxHeapify(arr, largest, n) ` ` `  `# This function basically builds max heap  ` `def` `convertMaxHeap(arr, n): ` `     `  `    ``# Start from bottommost and rightmost  ` `    ``# internal mode and heapify all  ` `    ``# internal modes in bottom up way  ` `    ``for` `i ``in` `range``(``int``((n ``-` `2``) ``/` `2``), ``-``1``, ``-``1``): ` `        ``MaxHeapify(arr, i, n) ` ` `  `# A utility function to print a  ` `# given array of given size  ` `def` `printArray(arr, size): ` `    ``for` `i ``in` `range``(size): ` `        ``print``(arr[i], end ``=` `" "``) ` `    ``print``() ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `'__main__'``: ` `     `  `    ``# array representing Min Heap  ` `    ``arr ``=` `[``3``, ``5``, ``9``, ``6``, ``8``, ``20``, ``10``, ``12``, ``18``, ``9``]  ` `    ``n ``=` `len``(arr) ` ` `  `    ``print``(``"Min Heap array : "``)  ` `    ``printArray(arr, n)  ` ` `  `    ``convertMaxHeap(arr, n)  ` ` `  `    ``print``(``"Max Heap array : "``)  ` `    ``printArray(arr, n) ` ` `  `# This code is contributed by PranchalK `

## C#

 `// C# program to convert  ` `// min Heap to max Heap ` `using` `System; ` ` `  `class` `GFG  ` `{ ` `    ``// To heapify a subtree with  ` `    ``// root at given index ` `    ``static` `void` `MaxHeapify(``int` `[]arr,  ` `                           ``int` `i, ``int` `n) ` `    ``{ ` `        ``int` `l = 2 * i + 1; ` `        ``int` `r = 2 * i + 2; ` `        ``int` `largest = i; ` `        ``if` `(l < n && arr[l] > arr[i]) ` `            ``largest = l; ` `        ``if` `(r < n && arr[r] > arr[largest]) ` `            ``largest = r; ` `        ``if` `(largest != i) ` `        ``{ ` `            ``// swap arr[i] and arr[largest] ` `            ``int` `temp = arr[i]; ` `            ``arr[i] = arr[largest]; ` `            ``arr[largest] = temp; ` `            ``MaxHeapify(arr, largest, n); ` `        ``} ` `    ``} ` ` `  `    ``// This function basically ` `    ``// builds max heap ` `    ``static` `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; i >= 0; --i) ` `            ``MaxHeapify(arr, i, n); ` `    ``} ` ` `  `    ``// A utility function to print  ` `    ``// a given array of given size ` `    ``static` `void` `printArray(``int` `[]arr,  ` `                           ``int` `size) ` `    ``{ ` `        ``for` `(``int` `i = 0; i < size; ++i) ` `            ``Console.Write(arr[i]+``" "``); ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``// array representing Min Heap ` `        ``int` `[]arr = {3, 5, 9, 6, 8,  ` `                     ``20, 10, 12, 18, 9}; ` `        ``int` `n = arr.Length; ` ` `  `        ``Console.Write(``"Min Heap array : "``); ` `        ``printArray(arr, n); ` ` `  `        ``convertMaxHeap(arr, n); ` ` `  `        ``Console.Write(````" Max Heap array : "````); ` `        ``printArray(arr, n); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

/div>

Output :

```Min Heap array : 3 5 9 6 8 20 10 12 18 9
Max Heap array : 20 18 10 12 9 9 3 5 6 8
```

The complexity of above solution might looks like O(nLogn) but it is O(n). Refer this G-Fact for more details.

Heap Heap