# Algorithm: Heap Sort
# Type: Sorting, Heap Data Structure
# Time Complexity: O(n log n)
# Space Complexity: O(1)

function heapSort(arr):
    buildMaxHeap(arr)
    for i from length(arr)-1 down to 1:
        swap(arr[0], arr[i])
        heapify(arr, 0, i)

function buildMaxHeap(arr):
    for i from floor(length(arr)/2) - 1 down to 0:
        heapify(arr, i, length(arr))

function heapify(arr, i, heapSize):
    largest = i
    left = 2*i + 1
    right = 2*i + 2

    if left < heapSize and arr[left] > arr[largest]:
        largest = left
    if right < heapSize and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        swap(arr[i], arr[largest])
        heapify(arr, largest, heapSize)