You are given an array arr of N integers representing a min Heap. The task is to convert it to max Heap.
A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node. 
Example 1:
Input:
N = 4
arr = [1, 2, 3, 4]
Output:
[4, 2, 3, 1]
Explanation:
The given min Heap:
          1
        /   \
      2       3
     /
   4
Max Heap after conversion:
         4
       /   \
      3     2
    /
   1
Example 2:
Input:
N = 5
arr = [3, 4, 8, 11, 13]
Output:
[13, 11, 8, 3, 4]
Explanation:
The given min Heap:
          3
        /   \
      4      8
    /   \ 
  11     13
Max Heap after conversion:
          13
        /    \
      11      8
    /   \ 
   3     4
 
Your Task:
Complete the function int convertMinToMaxHeap(), which takes integer N and array represented minheap as input and converts it to the array representing maxheap. You don't need to return or print anything, modify the original array itself.
Note: Only an unique solution is possible under the expected time complexity.
Expected Time Complexity: O(N * log N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def convertMinToMaxHeap(self, N, arr):

        # Code here

Solutions:
class Solution:

	def convertMinToMaxHeap(self, N, arr):

		def heapify(arr, i, N):
			largest = i
			l_child = 2 * i + 1
			r_child = 2 * i + 2
			if l_child < N and arr[largest] < arr[l_child]:
				largest = l_child
			if r_child < N and arr[largest] < arr[r_child]:
				largest = r_child
			if largest != i:
				(arr[largest], arr[i]) = (arr[i], arr[largest])
				heapify(arr, largest, N)
		for i in range(N - 1, -1, -1):
			heapify(arr, i, N)


class Solution:

	def fix(self, arr, k, n):
		while k < n:
			child = k * 2 + 1
			if child >= n:
				break
			largest = child
			if child + 1 < n and arr[child] < arr[child + 1]:
				largest = child + 1
			(arr[k], arr[largest]) = (arr[largest], arr[k])
			k = largest

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			self.fix(arr, i, N)


class Solution:

	def heapify(self, heap, i):
		left = 2 * i + 1
		right = 2 * i + 2
		if left < N and heap[i] < heap[left]:
			mini = left
		else:
			mini = i
		if right < N and heap[mini] < heap[right]:
			mini = right
		if i != mini:
			(heap[mini], heap[i]) = (heap[i], heap[mini])
			self.heapify(heap, mini)

	def convertMinToMaxHeap(self, N, arr):
		i = N // 2 - 1
		while i >= 0:
			self.heapify(arr, i)
			i -= 1


class Solution:

	def heapify(self, arr, n, index):
		target = index
		l = index * 2 + 1
		r = index * 2 + 2
		if l < len(arr) and arr[target] < arr[l]:
			target = l
		if r < len(arr) and arr[target] < arr[r]:
			target = r
		if target != index:
			(arr[index], arr[target]) = (arr[target], arr[index])
			self.heapify(arr, n, target)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(arr, N, i)
		return arr


from heapq import heappush, heappop

class Solution:

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			arr = self.heapify(i, N, arr)
		return arr

	def heapify(self, i, N, arr):
		while i < N:
			largest = i
			(idx1, idx2) = (2 * i + 1, 2 * i + 2)
			while idx1 < N and arr[idx1] > arr[largest]:
				largest = idx1
			while idx2 < N and arr[idx2] > arr[largest]:
				largest = idx2
			if largest == i:
				break
			(arr[i], arr[largest]) = (arr[largest], arr[i])
			i = largest
		return arr


class Solution:

	def heapify(self, arr, n, i):
		left = 2 * i + 1
		right = 2 * i + 2
		large = i
		if left < len(arr) and arr[large] < arr[left]:
			large = left
		if right < len(arr) and arr[large] < arr[right]:
			large = right
		if large != i:
			(arr[large], arr[i]) = (arr[i], arr[large])
			self.heapify(arr, n, large)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(arr, N, i)
		return arr


class Solution:

	def convertMinToMaxHeap(self, N, heap):
		curr_size = len(heap)
		for idx in range(len(heap) - 1, -1, -1):
			parent_idx = idx
			child_idx_1 = 2 * idx + 1
			child_idx_2 = 2 * idx + 2
			while True:
				max_idx = parent_idx
				if child_idx_1 < curr_size and heap[parent_idx] < heap[child_idx_1]:
					max_idx = child_idx_1
				if child_idx_2 < curr_size and heap[max_idx] < heap[child_idx_2]:
					max_idx = child_idx_2
				if max_idx != parent_idx:
					(heap[max_idx], heap[parent_idx]) = (heap[parent_idx], heap[max_idx])
				else:
					break
				parent_idx = max_idx
				child_idx_1 = 2 * parent_idx + 1
				child_idx_2 = 2 * parent_idx + 2


import heapq

class Solution:

	def convertMinToMaxHeap(self, N, arr):

		def heapify(arr, i):
			while i < N // 2:
				l = i * 2 + 1
				r = i * 2 + 2
				maxi = i
				if l < N and arr[l] > arr[maxi]:
					maxi = l
				if r < N and arr[r] > arr[maxi]:
					maxi = r
				if maxi == i:
					break
				(arr[i], arr[maxi]) = (arr[maxi], arr[i])
				i = maxi
		for i in range(N // 2 - 1, -1, -1):
			heapify(arr, i)


import heapq

class Solution:

	def maxHeapify(self, arr, N, i):
		largest = i
		(l, r) = (2 * i + 1, 2 * i + 2)
		if l < N and arr[largest] < arr[l]:
			largest = l
		if r < N and arr[largest] < arr[r]:
			largest = r
		if largest != i:
			(arr[i], arr[largest]) = (arr[largest], arr[i])
			self.maxHeapify(arr, N, largest)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2, -1, -1):
			self.maxHeapify(arr, N, i)


class Solution:

	def maxHeapify(self, arr, N, i):
		lc = 2 * i + 1
		rc = 2 * i + 2
		largest = i
		if lc < N and arr[lc] > arr[largest]:
			largest = lc
		if rc < N and arr[rc] > arr[largest]:
			largest = rc
		if largest != i:
			(arr[largest], arr[i]) = (arr[i], arr[largest])
			self.maxHeapify(arr, N, largest)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2, -1, -1):
			self.maxHeapify(arr, N, i)


class Solution:

	def heapify(self, heap, n, ind):
		target = ind
		left = 2 * ind + 1
		right = 2 * ind + 2
		if left < n and heap[left] > heap[target]:
			target = left
		if right < n and heap[right] > heap[target]:
			target = right
		if target != ind:
			(heap[target], heap[ind]) = (heap[ind], heap[target])
			self.heapify(heap, n, target)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(arr, N, i)
		return arr


class Solution:

	def convertMinToMaxHeap(self, N, arr):
		self.built(arr)

	def heapify(self, arr, i, n):
		lr = i
		(l, r) = (2 * i + 1, 2 * i + 2)
		if l < n and arr[l] > arr[lr]:
			lr = l
		if r < n and arr[r] > arr[lr]:
			lr = r
		if lr != i:
			(arr[i], arr[lr]) = (arr[lr], arr[i])
			self.heapify(arr, lr, n)

	def built(self, arr):
		n = len(arr)
		for i in range(n, -1, -1):
			self.heapify(arr, i, n)


class Solution:

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			left = 2 * i + 1
			right = 2 * i + 2
			largest = i
			if left < N and arr[left] > arr[largest]:
				largest = left
			if right < N and arr[right] > arr[largest]:
				largest = right
			if largest != i:
				(arr[i], arr[largest]) = (arr[largest], arr[i])
				j = largest
				while j < N // 2:
					left = 2 * j + 1
					right = 2 * j + 2
					largest = j
					if left < N and arr[left] > arr[largest]:
						largest = left
					if right < N and arr[right] > arr[largest]:
						largest = right
					if largest != j:
						(arr[j], arr[largest]) = (arr[largest], arr[j])
						j = largest
					else:
						break
		return arr


import heapq as hq

class Solution:

	def heapify(self, arr, n, ind):
		target = ind
		left = 2 * ind + 1
		right = 2 * ind + 2
		if left < len(arr) and arr[target] < arr[left]:
			target = left
		if right < len(arr) and arr[target] < arr[right]:
			target = right
		if target != ind:
			(arr[ind], arr[target]) = (arr[target], arr[ind])
			self.heapify(arr, n, target)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(arr, N, i)
		return arr


class Solution:

	def convertMinToMaxHeap(self, N, arr):

		def heapify(arr, n, i):
			(temp, left, right) = (i, 2 * i + 1, 2 * i + 2)
			if left < n and arr[left] > arr[temp]:
				temp = left
			if right < n and arr[right] > arr[temp]:
				temp = right
			if temp != i:
				(arr[i], arr[temp]) = (arr[temp], arr[i])
				heapify(arr, n, temp)

		def buildheap(arr, n):
			for i in range(n // 2 - 1, -1, -1):
				heapify(arr, n, i)
		buildheap(arr, N)
		return arr


class Solution:

	def heapify(self, n, ind, arr):
		res = ind
		(l, r) = (2 * ind + 1, 2 * ind + 2)
		if l < n and arr[res] < arr[l]:
			res = l
		if r < n and arr[res] < arr[r]:
			res = r
		if res != ind:
			(arr[ind], arr[res]) = (arr[res], arr[ind])
			self.heapify(n, res, arr)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(N, i, arr)
		return arr


from heapq import heappop, heappush, heapify

class Solution:

	def MaxHeapify(self, 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])
			self.MaxHeapify(arr, largest, N)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(int((N - 2) / 2), -1, -1):
			self.MaxHeapify(arr, i, N)


import typing as ty

class Solution:

	def convertMinToMaxHeap(self, N, arr):

		def heapify(iterable: ty.List[int], i=0):
			largest = i
			if 2 * i + 1 < len(iterable):
				if iterable[2 * i + 1] > iterable[i]:
					largest = 2 * i + 1
			if 2 * i + 2 < len(iterable):
				if iterable[2 * i + 2] > iterable[largest]:
					largest = 2 * i + 2
			if largest != i:
				(iterable[i], iterable[largest]) = (iterable[largest], iterable[i])
				heapify(iterable, largest)
			return iterable
		for i in range(N // 2 - 1, -1, -1):
			heapify(arr, i)
		return arr


class Solution:

	def heapify(self, arr, n, i):
		largest = i
		left = 2 * i + 1
		right = 2 * i + 2
		if left < n and arr[largest] < arr[left]:
			largest = left
		if right < n and arr[largest] < arr[right]:
			largest = right
		if largest != i:
			(arr[largest], arr[i]) = (arr[i], arr[largest])
			self.heapify(arr, n, largest)

	def convertMinToMaxHeap(self, n, arr):
		p = n // 2
		for i in range(p - 1, -1, -1):
			self.heapify(arr, n, i)


class Solution:

	def convertMinToMaxHeap(self, N, heap):

		def siftDown(i):
			left = 2 * i + 1
			right = 2 * i + 2
			while left < N and heap[i] < heap[left] or (right < N and heap[i] < heap[right]):
				largest = left if right >= N or heap[left] >= heap[right] else right
				(heap[largest], heap[i]) = (heap[i], heap[largest])
				i = largest
				left = 2 * i + 1
				right = 2 * i + 2
		for i in range(N - 1, -1, -1):
			siftDown(i)


class Solution:

	def heapify(self, arr, index):
		(l, r) = (2 * index + 1, 2 * index + 2)
		largest = index
		if l < len(arr) and arr[largest] < arr[l]:
			largest = l
		if r < len(arr) and arr[largest] < arr[r]:
			largest = r
		if arr[largest] != arr[index]:
			(arr[largest], arr[index]) = (arr[index], arr[largest])
			self.heapify(arr, largest)

	def convertMinToMaxHeap(self, N, arr):
		for i in range((N - 1) // 2, -1, -1):
			self.heapify(arr, i)


class Solution:

	def convertMinToMaxHeap(self, N, arr):
		nl = (N - 1) // 2
		while nl >= 0:
			self.downheapify(arr, nl, N)
			nl -= 1
		return arr

	def downheapify(self, arr, i, n):
		leftChild = 2 * i + 1
		rightChild = 2 * i + 2
		if i >= n or leftChild >= n:
			return
		minx = i
		if arr[leftChild] > arr[minx]:
			minx = leftChild
		if rightChild < n and arr[rightChild] > arr[minx]:
			minx = rightChild
		if minx == i:
			return
		(arr[i], arr[minx]) = (arr[minx], arr[i])
		self.downheapify(arr, minx, n)


from heapq import heappop

class Solution:

	def heapify(self, arr, i, n):
		while 2 * i + 1 < n:
			largest = 2 * i + 1
			if 2 * i + 2 < n and arr[largest] < arr[2 * i + 2]:
				largest = 2 * i + 2
			if arr[largest] > arr[i]:
				(arr[i], arr[largest]) = (arr[largest], arr[i])
				i = largest
			else:
				break

	def convertMinToMaxHeap(self, N, arr):
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(arr, i, N)


class Solution:

	def convertMinToMaxHeap(self, N, arr):

		def heapify(i):
			maxi = i
			if 2 * i + 1 < N and arr[2 * i + 1] > arr[maxi]:
				maxi = 2 * i + 1
			if 2 * i + 2 < N and arr[2 * i + 2] > arr[maxi]:
				maxi = 2 * i + 2
			if maxi != i:
				(arr[i], arr[maxi]) = (arr[maxi], arr[i])
				heapify(maxi)
		for i in range((N - 1) // 2, -1, -1):
			heapify(i)


def myHeapify(arr, n, indx):
	(largest, left, right) = (indx, 2 * indx + 1, 2 * indx + 2)
	if left < n and arr[left] > arr[largest]:
		largest = left
	if right < n and arr[right] > arr[largest]:
		largest = right
	if largest != indx:
		(arr[largest], arr[indx]) = (arr[indx], arr[largest])
		myHeapify(arr, n, largest)

class Solution:

	def convertMinToMaxHeap(self, N, arr):
		for i in range(int(N / 2), -1, -1):
			myHeapify(arr, N, i)
		return arr


class Solution:

	def convertMinToMaxHeap(self, N, arr):
		from math import floor

		def heapify(arr, i):
			left = 2 * i + 1
			right = 2 * i + 2
			largest = i
			if left >= 0 and left < N and (arr[left] > arr[largest]):
				largest = left
			if right >= 0 and right < N and (arr[right] > arr[largest]):
				largest = right
			if largest != i:
				(arr[i], arr[largest]) = (arr[largest], arr[i])
				heapify(arr, largest)
			return arr
		for i in range(floor(N / 2) - 1, -1, -1):
			arr = heapify(arr, i)
		return arr


class Solution:

	def convertMinToMaxHeap(self, N, arr):

		def heapify(arr, i):
			left = 2 * i + 1
			right = 2 * i + 2
			largest = i
			if left >= 0 and left < N and (arr[left] > arr[largest]):
				largest = left
			if right >= 0 and right < N and (arr[right] > arr[largest]):
				largest = right
			if largest != i:
				(arr[i], arr[largest]) = (arr[largest], arr[i])
				heapify(arr, largest)
			return arr
		for i in range(N - 1, -1, -1):
			arr = heapify(arr, i)
		return arr


import heapq

class Solution:

	def convertMinToMaxHeap(self, N, arr):

		def heapify(arr, ind):
			la = ind
			l = 2 * ind + 1
			r = 2 * ind + 2
			if l < N and arr[la] < arr[l]:
				la = l
			if r < N and arr[la] < arr[r]:
				la = r
			if la != ind:
				(arr[la], arr[ind]) = (arr[ind], arr[la])
				heapify(arr, la)
			return
		for i in range(N // 2, -1, -1):
			heapify(arr, i)


class Solution:

	def heapify(self, arr, n, i):
		large = i
		(l, r) = (2 * i + 1, 2 * i + 2)
		if l < n and arr[l] > arr[large]:
			large = l
		if r < n and arr[r] > arr[large]:
			large = r
		if large != i:
			(arr[large], arr[i]) = (arr[i], arr[large])
			self.heapify(arr, n, large)

	def convertMinToMaxHeap(self, n, arr):
		start = n // 2 - 1
		for i in range(start, -1, -1):
			self.heapify(arr, n, i)
		return arr


class Solution:

	def convertMinToMaxHeap(self, n, a):

		def down_heapify(a, i, n):
			pi = i
			lci = 2 * pi + 1
			rci = 2 * pi + 2
			while lci < n:
				mi = pi
				if a[mi] < a[lci]:
					mi = lci
				if rci < n and a[mi] < a[rci]:
					mi = rci
				if mi == pi:
					return
				(a[mi], a[pi]) = (a[pi], a[mi])
				pi = mi
				lci = 2 * pi + 1
				rci = 2 * pi + 2

		def heap_sort(a):
			n = len(a)
			for i in range(n // 2 - 1, -1, -1):
				down_heapify(a, i, n)
		t = heap_sort(a)
		return a


class Solution:

	def solve(self, arr, n, i):
		largest = i
		l = 2 * i + 1
		r = 2 * i + 2
		if l < n and arr[largest] < arr[l]:
			largest = l
		if r < n and arr[r] > arr[largest]:
			largest = r
		if largest != i:
			(arr[i], arr[largest]) = (arr[largest], arr[i])
			self.solve(arr, n, largest)

	def convertMinToMaxHeap(self, N, arr):
		index = N // 2 - 1
		for i in range(index, -1, -1):
			self.solve(arr, N, i)
		return arr


class Solution:

	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])
			Solution.MaxHeapify(arr, largest, N)

	def convertMinToMaxHeap(self, N, arr):
		for i in range(int((N - 2) / 2), -1, -1):
			Solution.MaxHeapify(arr, i, N)