def heapify(arr, n, i):
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2

  # Check if left child exists and is larger than root
  if left < n and arr[left]> arr[largest]:
    largest = left

  # Check if right child exists and is larger
  if right < n and arr[right]> arr[largest]:
    largest = right

  # If root is not largest, swap and continue heapifying
  if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

def heap_sort(arr):
  n = len(arr)

  # Step 1: Build max heap
  for i in range(n//2 - 1, -1, -1):
    heapify(arr, n, i)

  # Step 2: Extract elements from heap
  for i in range(n-1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i] # swap
    heapify(arr, i, 0)

# Example
arr = [12, 11, 13, 5, 6, 7]
print("Original:", arr)
heap_sort(arr)
print("Sorted:", arr)