Given an array of size N. The task is to sort the array elements by completing functions heapify() and buildHeap() which are used to implement Heap Sort.
Example 1:
Input:
N = 5
arr[] = {4,1,3,9,7}
Output:
1 3 4 7 9
Explanation:
After sorting elements
using heap sort, elements will be
in order as 1,3,4,7,9.
Example 2:
Input:
N = 10
arr[] = {10,9,8,7,6,5,4,3,2,1}
Output:
1 2 3 4 5 6 7 8 9 10
Explanation:
After sorting elements
using heap sort, elements will be
in order as 1, 2,3,4,5,6,7,8,9,10.
Your Task :
You don't have to read input or print anything. Your task is to complete the functions heapify(), buildheap() and heapSort() where heapSort() and buildheap() takes the array and it's size as input and heapify() takes the array, it's size and an index i as input. Complete and use these functions to sort the array using heap sort algorithm.
Note: You don't have to return the sorted list. You need to sort the array "arr" in place.
Expected Time Complexity: O(N * Log(N)).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    #Heapify function to maintain heap property.
    def heapify(self,arr, n, i):
        # code here
    
    #Function to build a Heap from array.
    def buildHeap(self,arr,n):
        # code here
    
    #Function to sort an array using Heap Sort.    
    def HeapSort(self, arr, n):
        #code here

Solutions:
class Solution:

	def heapify(self, arr, n, i):
		mi = i
		lc = 2 * i + 1
		rc = 2 * i + 2
		if lc < n and arr[mi] < arr[lc]:
			mi = lc
		if rc < n and arr[mi] < arr[rc]:
			mi = rc
		if mi != i:
			(arr[mi], arr[i]) = (arr[i], arr[mi])
			self.heapify(arr, n, mi)

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)
		return arr


class Solution:

	def heapify(self, arr, n, i):
		largest = i
		l_child = 2 * i + 2
		r_child = 2 * i + 1
		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 i != largest:
			(arr[largest], arr[i]) = (arr[i], arr[largest])
			self.heapify(arr, n, largest)

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(len(arr) - 1, -1, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)


class Solution:

	def heapify(self, arr, n, i):
		largest = i
		left = 2 * i + 1
		right = 2 * i + 2
		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])
			self.heapify(arr, n, largest)

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

	def HeapSort(self, arr, n):
		n = len(arr)
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)
		return arr


class Solution:

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

	def HeapSort(self, arr, n):
		for i in range(n // 2 - 1, -1, -1):
			self.heap(arr, n, i)
		for j in range(n - 1, 0, -1):
			(arr[j], arr[0]) = (arr[0], arr[j])
			self.heap(arr, j, 0)


class Solution:

	def heapify(self, arr, n, i):
		if 2 * i + 2 < n:
			s = max(arr[2 * i + 1], arr[2 * i + 2])
			if arr[i] < s:
				if arr[2 * i + 1] == s:
					(arr[i], arr[2 * i + 1]) = (arr[2 * i + 1], arr[i])
					self.heapify(arr, n, 2 * i + 1)
				else:
					(arr[i], arr[2 * i + 2]) = (arr[2 * i + 2], arr[i])
					self.heapify(arr, n, 2 * i + 2)
		elif 2 * i + 1 < n:
			if arr[i] < arr[2 * i + 1]:
				(arr[i], arr[2 * i + 1]) = (arr[2 * i + 1], arr[i])

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(len(arr)):
			(arr[0], arr[n - i - 1]) = (arr[n - i - 1], arr[0])
			self.heapify(arr, n - i - 1, 0)


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)


import heapq
from heapq import heappush, heappop

class Solution:

	def HeapSort(self, arr, n):
		new = []
		for num in arr:
			heappush(new, num)
		for i in range(n):
			arr[i] = heappop(new)


class Solution:

	def heapify(self, arr, n, i):
		p = (i - 1) // 2
		while i != 0 and arr[(i - 1) // 2] < arr[i]:
			(arr[i], arr[(i - 1) // 2]) = (arr[(i - 1) // 2], arr[i])
			i = (i - 1) // 2

	def buildHeap(self, arr, n):
		for i in range(n):
			self.heapify(arr, n, i)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		last = n - 1
		for i in range(n):
			(arr[0], arr[last]) = (arr[last], arr[0])
			self.down(last)
			last -= 1

	def down(self, req):
		i = 0
		while i * 2 + 2 < req and arr[i] < max(arr[i * 2 + 2], arr[i * 2 + 1]):
			if arr[i * 2 + 2] > arr[i * 2 + 1]:
				(arr[i], arr[i * 2 + 2]) = (arr[i * 2 + 2], arr[i])
				i = i * 2 + 2
			else:
				(arr[i], arr[i * 2 + 1]) = (arr[i * 2 + 1], arr[i])
				i = i * 2 + 1
		if i * 2 + 1 < req and arr[i] < arr[i * 2 + 1]:
			(arr[i], arr[i * 2 + 1]) = (arr[i * 2 + 1], arr[i])


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		j = n - 1
		while j >= 0:
			(arr[0], arr[j]) = (arr[j], arr[0])
			self.heapify(arr, j, 0)
			j -= 1


class Solution:

	def heapify(self, arr, n, i):
		pass

	def buildHeap(self, arr, n):
		pass

	def HeapSort(self, arr, n):
		return arr.sort()


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)
		return arr


from heapq import heapify, heappop

class Solution:

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

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

	def HeapSort(self, arr, n):
		size = n
		self.buildHeap(arr, n)
		while size > 0:
			(arr[size - 1], arr[0]) = (arr[0], arr[size - 1])
			size -= 1
			self.heapify(arr, size, 0)


class Solution:

	def leftChild(self, i):
		return 2 * i + 1

	def rightChild(self, i):
		return 2 * i + 2

	def parent(self, i):
		return (i - 1) // 2

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

	def heapUP(self, arr, n, i):
		if i == 0:
			return
		parent = self.parent(i)
		if arr[i] > arr[parent]:
			(arr[i], arr[parent]) = (arr[parent], arr[i])
			self.heapUp(arr, n, parent)

	def heapify(self, arr, n, i):
		self.heapUp(arr, n, i)
		self.heapDown(arr, n, i)

	def buildHeap(self, arr, n):
		for i in range(n // 2 - 1, -1, -1):
			self.heapDown(arr, n, i)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, -1, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapDown(arr, i, 0)


class Solution:

	def heappop(self, heap):
		if not heap:
			return None
		min_value = heap[0]
		heap[0] = heap[-1]
		heap.pop()
		current = 0
		self.heapify_down(heap, len(heap), current)
		return min_value

	def heapify_down(self, heap, n, current):
		left = 2 * current + 1
		right = 2 * current + 2
		small = current
		if left < n and heap[left] < heap[small]:
			small = left
		if right < n and heap[right] < heap[small]:
			small = right
		if small != current:
			(heap[current], heap[small]) = (heap[small], heap[current])
			self.heapify_down(heap, n, small)

	def heappush(self, heap, value):
		heap.append(value)
		current = len(heap) - 1
		self.heapify_up(heap, current)

	def heapify_up(self, heap, current):
		if current > 0:
			parent = (current - 1) // 2
			if heap[current] < heap[parent]:
				(heap[current], heap[parent]) = (heap[parent], heap[current])
			self.heapify_up(heap, parent)

	def buildHeap(self, arr, n):
		heap = []
		for i in range(n):
			self.heappush(heap, arr[i])
		return heap

	def HeapSort(self, arr, n):
		heap = self.buildHeap(arr, n)
		for i in range(n):
			arr[i] = self.heappop(heap)


import heapq

class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)
		return arr


class Solution:

	def swap(self, arr, l, r):
		(arr[l], arr[r]) = (arr[r], arr[l])

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

	def buildHeap(self, arr, n):
		for i in range((len(arr) - 2) // 2, -1, -1):
			self.heapify(arr, n, i)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, -1, -1):
			self.swap(arr, 0, i)
			self.heapify(arr, i, 0)


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)
		return arr.reverse()
		list = []
		for i in range(len(arr)):
			list.append(arr[0])
			arr[0] = arr[-1]
			arr.pop()
			self.heapify(arr, len(arr), 0)


class Solution:

	def heapify(self, arr, n, i):
		arr.sort()

	def buildHeap(self, arr, n):
		arr.sort()

	def HeapSort(self, arr, n):
		arr.sort()


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)


from heapq import heappop, heappush, heappushpop

class Solution:

	def heapify(self, arr, n, i):
		pass

	def buildHeap(self, arr, n):
		heap = []
		for i in arr:
			heappush(heap, i)
		for i in range(len(arr)):
			ele = heappop(heap)
			arr[i] = ele

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)


class Solution:

	def heapify(self, heap, current):
		while heap[(current - 1) // 2] > heap[current] and current > 0:
			(heap[(current - 1) // 2], heap[current]) = (heap[current], heap[(current - 1) // 2])
			current = (current - 1) // 2

	def buildHeap(self, arr, current, limit):
		(left, right) = (2 * current + 1, 2 * current + 2)
		while current < limit and left < limit and (arr[current] > arr[left]) or (right < limit and arr[current] > arr[right]):
			if arr[left] < arr[right]:
				(arr[current], arr[left]) = (arr[left], arr[current])
				current = left
			else:
				(arr[current], arr[right]) = (arr[right], arr[current])
				current = right
			(left, right) = (current * 2 + 1, current * 2 + 2)

	def HeapSort(self, arr, n):
		for i in range(len(arr)):
			arr[i] = -1 * arr[i]
			self.heapify(arr, i)
		for i in range(len(arr)):
			target = len(arr) - i - 1
			(arr[0], arr[target]) = (arr[target], -arr[0])
			self.buildHeap(arr, 0, len(arr) - i)


class Solution:

	def heapify(self, arr, n, i):
		curr = i
		cl = curr * 2 + 1
		cr = curr * 2 + 2
		if cl < n and arr[cl] > arr[curr]:
			curr = cl
		if cr < n and arr[cr] > arr[curr]:
			curr = cr
		if curr != i:
			self.swap(arr, curr, i)
			self.heapify(arr, n, curr)

	def swap(self, arr, i, j):
		(arr[i], arr[j]) = (arr[j], arr[i])

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		i = n - 1
		while i > 0:
			self.swap(arr, 0, i)
			self.heapify(arr, i, 0)
			i -= 1


class Solution:

	def heapify(self, arr, n, i):
		left = 2 * i + 1
		right = 2 * i + 2
		while n > left and arr[i] < arr[left] or (n > right and arr[i] < arr[right]):
			if n > left and n > right:
				if arr[left] > arr[right]:
					max_child = left
				else:
					max_child = right
			elif n > left:
				max_child = left
			else:
				max_child = right
			(arr[i], arr[max_child]) = (arr[max_child], arr[i])
			i = max_child
			left = 2 * i + 1
			right = 2 * i + 2

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, -1, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)


class Solution:

	def swap(self, arr, left, right):
		(arr[left], arr[right]) = (arr[right], arr[left])

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

	def buildHeap(self, arr, n):
		for idx in range(n // 2 - 1, -1, -1):
			self.heapify(arr, n, idx)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for idx in range(n - 1, -1, -1):
			self.swap(arr, 0, idx)
			self.heapify(arr, idx, 0)


class Solution:

	def heapify(self, arr, n, i):
		maximum = i
		while True:
			left = 2 * i + 1
			right = 2 * i + 2
			if left <= n and arr[left] > arr[maximum]:
				maximum = left
			if right <= n and arr[maximum] < arr[right]:
				maximum = right
			if maximum != i:
				(arr[i], arr[maximum]) = (arr[maximum], arr[i])
				self.heapify(arr, n, maximum)
				return
			else:
				return

	def buildHeap(self, arr, n):
		for i in range(len(arr) // 2 - 1, -1, -1):
			self.heapify(arr, n, i)

	def HeapSort(self, arr, n):
		n = len(arr) - 1
		self.buildHeap(arr, n)
		while n >= 1:
			(arr[0], arr[n]) = (arr[n], arr[0])
			self.heapify(arr, n - 1, 0)
			n -= 1


class Solution:

	def heapify(self, arr, n, i):
		smallchild = i
		leftChild = 2 * i + 1
		rightChild = 2 * i + 2
		if leftChild < n and arr[leftChild] > arr[smallchild]:
			smallchild = leftChild
		if rightChild < n and arr[rightChild] > arr[smallchild]:
			smallchild = rightChild
		if smallchild != i:
			(arr[i], arr[smallchild]) = (arr[smallchild], arr[i])
			self.heapify(arr, n, smallchild)

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)


import heapq

class Solution:

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

	def buildHeap(self, arr, n):
		heapq._heapify_max(arr)
		return arr

	def HeapSort(self, arr, n):
		arr = self.buildHeap(arr, n)
		i = len(arr) - 1
		j = 0
		while i > j:
			(arr[i], arr[j]) = (arr[j], arr[i])
			n = n - 1
			self.heapify(arr, n, j)
			i -= 1
		return arr


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n):
			(arr[0], arr[n - 1 - i]) = (arr[n - 1 - i], arr[0])
			self.heapify(arr, n - 1 - i, 0)


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, -1, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, i, 0)


class Solution:

	def __init__(self):
		self.heap = []

	def swap(self, heap, i, j):
		(heap[i], heap[j]) = (heap[j], heap[i])

	def heapify_down(self, heap, n, i):
		small_child = i
		left = 2 * i + 1
		right = 2 * i + 2
		if left < n and heap[left] > heap[small_child]:
			small_child = left
		if right < n and arr[right] > heap[small_child]:
			small_child = right
		if small_child != i:
			self.swap(heap, i, small_child)
			self.heapify_down(heap, n, small_child)

	def buildHeap(self, heap, n):
		for i in range(n // 2 - 1, -1, -1):
			self.heapify_down(heap, n, i)

	def HeapSort(self, heap, n):
		self.buildHeap(heap, n)
		for i in range(n - 1, 0, -1):
			self.swap(heap, i, 0)
			self.heapify_down(heap, i, 0)


class Solution:

	def heappush(self, arr, ele):
		arr.append(ele)
		self.heapify_up(arr, len(arr) - 1)

	def heapify_up(self, arr, current):
		if current == 0:
			return
		parent = (current - 1) // 2
		if current > 0 and arr[current] < arr[parent]:
			(arr[current], arr[parent]) = (arr[parent], arr[current])
			self.heapify_up(arr, parent)

	def heappop(self, arr):
		popped = arr[0]
		arr[0] = arr[-1]
		arr.pop()
		self.heapify_down(arr, 0)
		return popped

	def heapify_down(self, arr, current):
		if current >= len(arr):
			return
		minimum = current
		left = 2 * current + 1
		right = 2 * current + 2
		if left < len(arr) and arr[left] < arr[minimum]:
			minimum = left
		if right < len(arr) and arr[right] < arr[minimum]:
			minimum = right
		if minimum != current:
			(arr[current], arr[minimum]) = (arr[minimum], arr[current])
			self.heapify_down(arr, minimum)

	def buildHeap(self, arr, n):
		arr2 = []
		for num in arr:
			self.heappush(arr2, num)
		for i in range(n):
			arr[i] = self.heappop(arr2)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)


class Solution:

	def heapify(self, arr, n, index, index2=None):
		(left, right) = (2 * index + 1, 2 * index + 2)
		childIndex = right if right < index2 and arr[right] > arr[left] else left
		try:
			while childIndex < index2 and arr[index] < arr[childIndex]:
				(arr[index], arr[childIndex]) = (arr[childIndex], arr[index])
				index = childIndex
				(left, right) = (2 * index + 1, 2 * index + 2)
				childIndex = right if right < index2 and arr[right] > arr[left] else left
		except:
			return

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, -1, -1):
			(arr[0], arr[i]) = (arr[i], arr[0])
			self.heapify(arr, n, 0, i)


class Solution:

	def heapifyPush(self, heap, val):
		heap.append(val)
		self.heapifyUp(heap, len(heap) - 1)

	def heapifyUp(self, heap, curr):
		par = (curr - 1) // 2
		if curr > 0 and heap[par] > heap[curr]:
			(heap[par], heap[curr]) = (heap[curr], heap[par])
			self.heapifyUp(heap, par)

	def heapPop(self, heap):
		(heap[0], heap[-1]) = (heap[-1], heap[0])
		temp = heap.pop()
		self.heapifyDown(heap, 0)
		return temp

	def heapifyDown(self, heap, curr):
		left = 2 * curr + 1
		right = 2 * curr + 2
		if left >= len(heap):
			return
		elif right >= len(heap):
			if heap[left] >= heap[curr]:
				return
			(heap[left], heap[curr]) = (heap[curr], heap[left])
			self.heapifyDown(heap, left)
		else:
			temp = left if heap[left] < heap[right] else right
			if heap[temp] >= heap[curr]:
				return
			(heap[temp], heap[curr]) = (heap[curr], heap[temp])
			self.heapifyDown(heap, temp)

	def HeapSort(self, arr, n):
		heap = []
		for i in arr:
			self.heapifyPush(heap, i)
		for i in range(len(arr)):
			arr[i] = self.heapPop(heap)


import heapq

class Solution:

	def leftchild(self, current):
		return current * 2 + 1

	def rightchild(self, current):
		return current * 2 + 2

	def swap(self, arr, c, n):
		(arr[c], arr[n]) = (arr[n], arr[c])

	def heapify(self, arr, n, current):
		if self.leftchild(current) < n:
			l = self.leftchild(current)
			r = self.rightchild(current)
			smallest = current
			if arr[l] > arr[smallest]:
				smallest = l
			if r < n and arr[r] > arr[smallest]:
				smallest = r
			if smallest != current:
				self.swap(arr, current, smallest)
				self.heapify(arr, n, smallest)

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, len(arr))
		n = len(arr)
		while n:
			self.swap(arr, 0, n - 1)
			n -= 1
			self.heapify(arr, n, 0)


class Solution:

	def heapPop(self, arr):
		value = arr[0]
		(arr[0], arr[-1]) = (arr[-1], arr[0])
		arr.pop()
		if arr:
			self.heapify(arr, len(arr), 0)
		return value

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

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

	def HeapSort(self, arr, n):
		sorted_list = []
		self.buildHeap(arr, len(arr))
		while arr:
			sorted_list.append(self.heapPop(arr))
		for val in sorted_list:
			arr.append(val)


class Solution:

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

	def buildHeap(self, arr, n):
		for i in range(n // 2 - 1, -1, -1):
			self.heapifyDown(arr, n, i)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			self.heapifyDown(arr, i + 1, 0)
			(arr[i], arr[0]) = (arr[0], arr[i])


class Solution:

	def heapify(self, arr, n, i):
		temp = i
		left = 2 * i + 1
		right = 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[temp], arr[i]) = (arr[i], arr[temp])
			self.heapify(arr, n, temp)

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


from heapq import heappop

class Solution:

	def heapify(self, arr, n, i):
		largest = i
		left = 2 * i + 1
		right = 2 * i + 2
		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])
			self.heapify(arr, n, largest)

	def buildHeap(self, arr, n):
		leng = len(arr)
		for idx in range(leng - 1, -1, -1):
			self.heapify(arr, n, idx)

	def HeapSort(self, arr, n):
		ans = []
		self.buildHeap(arr, n)
		leng = len(arr)
		while leng > 0:
			(arr[0], arr[leng - 1]) = (arr[leng - 1], arr[0])
			leng -= 1
			self.heapify(arr, leng, 0)


class Solution:

	def heapify(self, arr, n, i):
		current = i
		greatest = current
		left = current * 2 + 1
		right = current * 2 + 2
		while True:
			if left < n and arr[left] > arr[greatest]:
				greatest = left
			if right < n and arr[right] > arr[greatest]:
				greatest = right
			if greatest == current:
				break
			(arr[greatest], arr[current]) = (arr[current], arr[greatest])
			left = greatest * 2 + 1
			right = greatest * 2 + 2
			current = greatest

	def buildHeap(self, arr, n):
		pass

	def HeapSort(self, arr, n):
		for i in range(n // 2 - 1, -1, -1):
			self.heapify(arr, n, i)
		for i in range(n - 1, -1, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)


class Solution:

	def heapify(self, arr, n, i):
		left = 1
		right = 2
		p = 0
		flag = True
		while flag:
			flag = False
			greater_child = p
			if left < i and arr[greater_child] < arr[left]:
				greater_child = left
			if right < i and arr[greater_child] < arr[right]:
				greater_child = right
			if greater_child != p:
				(arr[greater_child], arr[p]) = (arr[p], arr[greater_child])
				p = greater_child
				left = 2 * p + 1
				right = 2 * p + 2
				flag = True

	def buildHeap(self, arr, n):
		for i in range(n // 2, -1, -1):
			left = 2 * i + 1
			right = 2 * i + 2
			p = i
			flag = True
			while flag:
				flag = False
				greater_child = p
				if left < n and arr[greater_child] < arr[left]:
					greater_child = left
				if right < n and arr[greater_child] < arr[right]:
					greater_child = right
				if greater_child != p:
					(arr[greater_child], arr[p]) = (arr[p], arr[greater_child])
					p = greater_child
					left = 2 * p + 1
					right = 2 * p + 2
					flag = True

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1):
			(arr[0], arr[n - 1 - i]) = (arr[n - 1 - i], arr[0])
			self.heapify(arr, n, n - 1 - i)


class Solution:

	def down_heap(self, arr, n, i):
		while True:
			(l, r) = (2 * i + 1, 2 * i + 2)
			nxt = i if r >= n or arr[i] > arr[r] else r
			nxt = nxt if l >= n or arr[nxt] > arr[l] else l
			if nxt == i:
				break
			(arr[nxt], arr[i]) = (arr[i], arr[nxt])
			i = nxt

	def buildHeap(self, arr, n):
		for _ in range(n // 2 - 1, -1, -1):
			self.down_heap(arr, n, _)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for _ in range(n - 1, -1, -1):
			(arr[_], arr[0]) = (arr[0], arr[_])
			self.down_heap(arr, _, 0)


class Solution:

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

	def buildHeap(self, arr, n):
		for x in range(len(arr) - 1, -1, -1):
			self.heapify(arr, n, x)
		return arr

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		index = len(arr) - 1
		for x in range(n):
			(arr[0], arr[index]) = (arr[index], arr[0])
			self.heapify(arr, index, 0)
			index -= 1


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n):
			(arr[0], arr[n - i - 1]) = (arr[n - i - 1], arr[0])
			self.heapify_down(arr, n - i - 1, 0)


class Solution:

	def heapify(self, arr, n, i):
		current = i
		while current < n:
			left_child = 2 * current + 1
			right_child = 2 * current + 2
			smallest = current
			if left_child < n and arr[left_child] >= arr[smallest]:
				smallest = left_child
			if right_child < n and arr[right_child] > arr[smallest]:
				smallest = right_child
			if smallest == current:
				break
			(arr[smallest], arr[current]) = (arr[current], arr[smallest])
			current = smallest

	def buildHeap(self, arr, n):
		for index in range(len(arr) // 2 - 1, -1, -1):
			self.heapify(arr, n, index)

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for index in range(n - 1, 0, -1):
			(arr[0], arr[index]) = (arr[index], arr[0])
			self.heapify(arr, index, 0)


class Solution:

	def heapify(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[largest] < arr[r]:
			largest = r
		if largest != i:
			(arr[i], arr[largest]) = (arr[largest], arr[i])
			self.heapify(arr, n, largest)

	def HeapSort(self, arr, n):
		N = len(arr)
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(arr, N, i)
		for i in range(N - 1, -1, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		for i in range(n - 1, 0, -1):
			(arr[i], arr[0]) = (arr[0], arr[i])
			self.heapify(arr, i, 0)


class Solution:

	def heapify(self, arr, n):
		starting = len(arr) // 2 - 1
		for i in range(starting, -1, -1):
			self.heapify_down(arr, n, i)

	def heapify_down(self, arr, n, curr):
		Max_val = curr
		left = curr * 2 + 1
		right = curr * 2 + 2
		if left < n and arr[left] > arr[Max_val]:
			Max_val = left
		if right < n and arr[right] > arr[Max_val]:
			Max_val = right
		if arr[Max_val] != arr[curr]:
			(arr[Max_val], arr[curr]) = (arr[curr], arr[Max_val])
			self.heapify_down(arr, n, Max_val)

	def buildHeap(self, arr, n):
		self.heapify(arr, len(arr))

	def HeapSort(self, arr, n):
		length = len(arr)
		self.buildHeap(arr, length)
		i = 1
		while i < len(arr):
			(arr[0], arr[length - i]) = (arr[length - i], arr[0])
			self.heapify_down(arr, length - i, 0)
			i += 1


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		(arr[n - 1], arr[0]) = (arr[0], arr[n - 1])
		for i in range(1, n):
			last = n - i - 1
			self.heapify(arr, n - i, 0)
			(arr[last], arr[0]) = (arr[0], arr[last])
		return arr


class Solution:

	def heapify(self, arr, n, current):
		smallest = arr[0]
		self.Swap(arr, 0, len(arr) - 1)
		arr.pop()
		leftIndex = self.LeftChild(arr, current)
		rightIndex = self.RightChild(arr, current)
		while leftIndex < n and arr[leftIndex] < arr[current] or (rightIndex < n and arr[rightIndex] < arr[current]):
			if leftIndex < n and rightIndex < n:
				if arr[leftIndex] < arr[rightIndex]:
					self.Swap(arr, leftIndex, current)
					current = leftIndex
				else:
					self.Swap(arr, rightIndex, current)
					current = rightIndex
			else:
				self.Swap(arr, leftIndex, current)
				current = leftIndex
			leftIndex = self.LeftChild(arr, current)
			rightIndex = self.RightChild(arr, current)
		return smallest

	def buildHeap(self, arr, n):
		heap = []
		for num in arr:
			heap.append(num)
			self.heapifyUp(heap, len(heap) - 1)
		return heap

	def heapifyUp(self, heap, current):
		parent = self.parent(heap, current)
		if current > 0 and heap[parent] > heap[current]:
			self.Swap(heap, current, parent)
			self.heapifyUp(heap, parent)

	def HeapSort(self, arr, n):
		heap = self.buildHeap(arr, len(arr))
		result = []
		size = len(heap)
		for i in range(size):
			smallest = self.heapify(heap, len(heap) - 1, 0)
			arr[i] = smallest

	def LeftChild(self, arr, i):
		return 2 * i + 1

	def RightChild(self, arr, i):
		return 2 * i + 2

	def parent(self, arr, i):
		return (i - 1) // 2

	def Swap(self, heap, parent, current):
		(heap[parent], heap[current]) = (heap[current], heap[parent])


class Solution:

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

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

	def HeapSort(self, arr, n):
		self.buildHeap(arr, n)
		last = n - 1
		while last > 0:
			(arr[0], arr[last]) = (arr[last], arr[0])
			self.heapify(arr, last, 0)
			last -= 1


class Solution:

	def heapify(self, arr, n, i):
		self.heapUp(arr, i)
		self.heapDown(arr, i, n)

	def buildHeap(self, arr, n):
		pass

	def HeapSort(self, arr, n):
		for (i, val) in enumerate(arr):
			self.heapUp(arr, i)
		while n:
			(arr[0], arr[n - 1]) = (arr[n - 1], arr[0])
			n = n - 1
			self.heapDown(arr, 0, n)

	def remove(self, arr, n):
		return n

	def leftChild(self, arr, i, n):
		return i * 2 + 1

	def rightChild(self, arr, i, n):
		return i * 2 + 2

	def parent(self, arr, i, n):
		return (i - 1) // 2

	def heapUp(self, arr, i):
		par = (i - 1) // 2
		while i and arr[par] <= arr[i]:
			(arr[i], arr[par]) = (arr[par], arr[i])
			i = par
			par = (i - 1) // 2

	def heapDown(self, arr, i, n):
		while 2 * i + 1 < n:
			left = 2 * i + 1
			right = 2 * i + 2 if 2 * i + 2 < n else i
			minChild = max(left, right, key=lambda x: arr[x])
			if arr[i] >= arr[minChild]:
				break
			(arr[i], arr[minChild]) = (arr[minChild], arr[i])
			i = minChild


class Solution:

	def heapify_up(self, arr, i):
		parent = (i - 1) // 2
		if arr[i] > arr[parent] and i:
			(arr[i], arr[parent]) = (arr[parent], arr[i])
			self.heapify_up(arr, parent)

	def heapify_down(self, arr, n, curr):
		Max_val = curr
		left = curr * 2 + 1
		right = curr * 2 + 2
		if left < n and arr[left] > arr[Max_val]:
			Max_val = left
		if right < n and arr[right] > arr[Max_val]:
			Max_val = right
		if arr[Max_val] != arr[curr]:
			(arr[Max_val], arr[curr]) = (arr[curr], arr[Max_val])
			self.heapify_down(arr, n, Max_val)

	def buildHeap(self, arr, n):
		newarr = [arr[0]]
		for (i, val) in enumerate(arr):
			if i == 0:
				continue
			newarr.append(val)
			self.heapify_up(newarr, len(newarr) - 1)
		return newarr

	def HeapSort(self, arr, n):
		length = len(arr)
		values = self.buildHeap(arr, len(arr))
		for (i, val) in enumerate(values):
			arr[i] = val
		i = 1
		while i < len(arr):
			(arr[0], arr[length - i]) = (arr[length - i], arr[0])
			self.heapify_down(arr, length - i, 0)
			i += 1


class Solution:

	def heapify(self, arr, n, i):
		self.heapify_up(arr, n, i)
		self.heapify_down(arr, n, i)

	def heapify_up(self, arr, n, i):
		while i > 0 and arr[(i - 1) // 2] > arr[i]:
			(arr[(i - 1) // 2], arr[i]) = (arr[i], arr[(i - 1) // 2])
			i = (i - 1) // 2

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

	def buildHeap(self, arr, n):
		for i in range(n - 1, -1, -1):
			heapify(arr, n, i)

	def HeapSort(self, arr, n):
		arr.sort()


class Solution:

	def heapifyDown(self, arr, n, i):
		current = i
		while True:
			left = 2 * current + 1
			right = 2 * current + 2
			if left >= n:
				left = None
			if right >= n:
				right = None
			if left and right:
				if arr[left] < arr[right]:
					if arr[left] < arr[current]:
						(arr[left], arr[current]) = (arr[current], arr[left])
						current = left
					else:
						return arr
				elif arr[right] < arr[current]:
					(arr[right], arr[current]) = (arr[current], arr[right])
					current = right
				else:
					return arr
			elif right:
				if arr[right] < arr[current]:
					(arr[right], arr[current]) = (arr[current], arr[right])
					current = right
				else:
					return arr
			elif left:
				if arr[left] < arr[current]:
					(arr[left], arr[current]) = (arr[current], arr[left])
					current = left
				else:
					return arr
			else:
				return arr

	def buildHeap(self, arr, n):
		heap = arr.copy()
		for ind in range(n - 1, -1, -1):
			heap = self.heapifyDown(heap, n, ind)
		return heap

	def HeapSort(self, arr, n):
		tmpArr = arr.copy()
		heap = self.buildHeap(tmpArr, n)
		i = 0
		while heap:
			(heap[0], heap[-1]) = (heap[-1], heap[0])
			arr[i] = heap.pop()
			heap = self.heapifyDown(heap, len(heap), 0)
			i += 1
		return arr