Heapsort: In-place Sorting

Each time we remove an element from the heap, it's the largest item in the underlying array. So, in sorted order, it belongs at the end of the array. As we'll see, removing an item from the heap conveniently frees up space at the end of the underlying array where we can put the removed item

This reduces the $O(n)$ auxiliary space to $O(1)$.