def heapSort(arr):
  n = len(arr)
  # Create MaxHeap
  for i in range(n // 2 -1, -1, -1):
      heapify(arr, n, i)
  
  # Place max elements to back array one by one
  for i in range(n-1, -1, -1):
      arr[i], arr[0] = arr[0], arr[i]
      heapify(arr, i, 0)
  return arr

def heapify(arr, size, i):
  largest = i
  left = 2*i+1
  right = 2*i+2
  
  if left < size and arr[left] > arr[largest]:
      largest = left
  
  if right < size and arr[right] > arr[largest]:
      largest = right
  
  # Swap needed with child node
  if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, size, largest)