Historically heaps was first presented as a tool mainly for sorting in [8], and sorting does indeed remain one of the important applications of heaps. Sorting is achieved in two passes.- First a heap is build with all elements to be sorted, and next the elements are extracted one at a time. Since a heap always returns the largest element in the heap, this procedure will extract the elements in descending order.
By overlaying the heap and the output area, inplace sorting can be achieved. The algorithm to empty the heap is seen in listing 2.6.
Because the siftdown procedure runs in 
time, it is seen
that the running time of heapsort is 
both in the worst
case and in the average case.
