HeapSort

Psydocode

HeapSort(H,i,n)

for i := [n/2] to 1 do
  Heapify( H , i , n )
for i := n to 2 do
  change( H[1] , H[r] )
  Heapify( H , i , n - 1 )

Heapify(H,i,r)

if 2i <= r and H[2i] > H[r] then
  x := 2i
else
  x := i
if 2i + 1 <= r and H[2i + 1] > H[x] then
  x := 2i + 1
if i < x then
  change( H[x] , H[i] )
  Heapify( H , x , r )