Heapsort
More notes coming soon!
Naïve Heapsort

Naïve Heapsort is a variant of selection sort. It uses a heapbased priority queue to sort the items. To do this, insert all items into a maxheap and then remove them one by one. (It is also possible to use a minheap instead.) The first such item removed is placed at the end of the array, the next item right before the end, and so forth until that last item deleted is placed in position 0 of the array. Each insertion and deletion takes $O(\log N)$ time and there are $N$ insertions and deletions, resulting in a $O(N \log N)$ runtime. With some more work, we can show that heapsort is $\Theta(N \log N)$ in the worst case. This naïve version of heapsort uses $\Theta(N)$ space for the priority queue.
Inplace heapsort

When sorting an array, we can avoid the $\Theta(N)$ memory cost by treating the array itself as a heap. To do this, we first heapify the array using bottomup heap construction (taking $\Theta(N)$ time). We then repeatedly delete the max item, swapping it with the last item in the heap. Over time, the heap shrinks from $N$ items to 0 items, and the sorted list grows from 0 items to $N$ items. The resulting version is also $\Theta(N \log N)$.