Heapsort

We have already seen that a Heap can store a set of items and return the smallest one, in O(log(n)) time per item.

Therefore, an easy way to sort would be to put all the items into a heap, then remove items one at a time with deleteMin and put them into the output array.

The problem with this easy method is that it uses an extra array. However, we can do it using the original array:

1. Make the original array into a max heap. This can be done in O(n) time.

2. For the size of the heap,

   1. Remove the largest item from the heap. This makes the heap smaller, so that there is a hole at the end of the heap.

   2. Put the largest item into the hole.

This gives a sort in O(n · log(n)) time. Heapsort is in-place, but not stable.