5.2 Heap sort

The prototype of an inplace heap sort should be as follows:

Here, array is a pointer pointing to the first location of the integer array (to be sorted), and n specifies the number of elements in the array.

The implementation of the heap sort algorithm should attach the heap to the array, then add values in the array to the heap from the beginning of array to the end. Then, the algorithm should remove values from the heap and repopulate the array from the end of array to the beginning.