HeapSort(arr, n):

// 1. Build Max-Heap

for i = n/2 - 1 down to 0:

siftDown(arr, n, i)

siftDown(arr, n, i):

largest = i; left = 2i+1; right = 2i+2

if left < n && arr[left] > arr[largest]: largest = left

if right < n && arr[right] > arr[largest]: largest = right

if largest != i:

swap(arr[i], arr[largest])

siftDown(arr, n, largest)

// 2. Extract Max

for i = n-1 down to 1:

swap(arr[0], arr[i])

siftDown(arr, i, 0) // heap limit = i