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 O(logN) time, it is seen that the running time of heapsort is O(NlogN) both in the worst case and in the average case.
