def heap_sort(arr):
n = len(arr)
# Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements from the heap one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
def heapify(arr, n, i):
largest = i # Initialize largest as root
left = 2 * i + 1 # left = 2*i + 1
right = 2 * i + 2 # right = 2*i + 2
# Check if left child of root exists and is greater than root
if left < n and arr[left] > arr[largest]:
largest = left
# Check if right child of root exists and is greater than root
if right < n and arr[right] > arr[largest]:
largest = right
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
heapify(arr, n, largest)