Pseudo Code

siftDown(array, i, size):
   loop:
      largest = i
      left = 2*i + 1
      right = 2*i + 2
      if left < size and array[left] > array[largest]:  largest = left
      if right < size and array[right] > array[largest]: largest = right
      if largest == i: stop
      swap array[i] and array[largest]
      i = largest

heapSort(array):
   n = length(array)
   for i from n/2 - 1 down to 0:   # build max-heap
      siftDown(array, i, n)
   for end from n-1 down to 1:     # extract max repeatedly
      swap array[0] and array[end]
      siftDown(array, 0, end)