Heap Sort Algorithm

/* build a heap */

for each element x in S {

add x to the end of the heap;

bubbleUp x;

}

/* use the heap to generate a sorted sequence */

while the heap is not empty {

delete and output the root of the heap;

move the end of the heap x to the root;

bubbleDown x;

}