This is a heapsort I did from memory a few days ago. The main thing about it is that the array starts out with 0 items in the heap, where everything is in the array, unsorted. Then, using no extra space, move each item into the heap, and ensure that the parent is never less than any child. By the time we have put everything into the heap, it is "heapified". It is a priority queue, where the item at the top, at index 0 is the greatest element.
We then swap out the greatest item to the next item in the list, from the right. Every time we remove an element, we make sure that the top item bubbles down, until