Heapsort
Suppose we want to put an array of numbers into increasing order (sort them). How would you do it? You would probably come up with something which is O(n^2). Could we use a heap to make this faster?
On the surface, heapsort is very easy: load everything into your heap, then pull it out, one by one. They'll come back out in order. Loading everything in? If we do it bottom-up, it's O(n). Taking everything out? O(n log(n)). So, total runtime O(n log(n)). But, it seemingly requires two arrays!
Consider the following sequence of numbers: 0 2 6 5 3 1 4. We'd like to put these in increasing order. Let's start by heapifying in place. I'll put a | in the array; everything to the right of it has been heapified, everything to the left has not.
We start by putting the last (n+1)/2 things onto the bottom level of the heap; this doesn't require any work: 0 2 6|5 3 1 4. We then put the next (n+1)/4 things on the next level, then fix the two mini-heaps:
- 0|2 6 5 3 1 4
- 0|5 6 2 3 1 4 (2 has bubbled down).
- 0 2 6 5 3 1 4
- 6 5 0 2 3 1 4 (0 has bubbled down once).
- 6 5 4 2 3 1 0 (0 has bubbled down again).
Now, we can do removeMaxs. Here's the first one. Now, the | will mean everything to the right is sorted, and everything to the left is still in the heap.
- 6 5 4 2 3 1 0
- 0 5 4 2 3 1|6 (swapped the last thing with the top thing)
- 5 0 4 2 3 1|6 (0 has bubbled down)
- 5 3 4 2 0 1|6 (0 has bubbled down again)
Do another removeMax, again swapping the top thing for the last thing:
- 5 3 4 2 0 1|6
- 1 3 4 2 0|5 6 (Swap the 1 and the 5)
- 4 3 1 2 0|5 6 (1 has bubbled down)
Again:
- 4 3 1 2 0|5 6
- 0 3 1 2|4 5 6 (swap the 4 and the 0)
- 3 0 1 2|4 5 6 (0 has bubbled down)
- 3 2 1 0|4 5 6 (0 has bubbled down)
Again:
- 3 2 1 0|4 5 6
- 0 2 1|3 4 5 6 (swap the 0 and the 3)
- 2 0 1|3 4 5 6 (0 has bubbled down)
Again:
- 2 0 1|3 4 5 6
- 1 0|2 3 4 5 6 (swap the 1 and the 2)
Again:
- 1 0|2 3 4 5 6
- 0 1 2 3 4 5 6 (swap, and we're sorted)
O(n log(n)), in place! It turns out this is the absolute best we can do in comparison-based sort.
By the way, the typical O(n^2) sort, the algorithm most people come up with on their own, is called bubble sort. Don't use it! Your commander-in-chief would be disappointed.