Following up on my quicksort and merge sort blog posts, I’m now going dive into the heap sort. I found the heap sort to be a tad more obtuse than the other basic sorts, and I think the main reason is we’re moving on from just using arrays and introducing another data structure: the heap…but also arrays.
A binary heap is a complete tree in which all parent elements are either larger than their children, in the case of a Max Heap, or smaller in the case of a Min Heap. Complete just means that all levels in the tree are completely filled, with the possible exception of the last, and that the elements in that last level are stored as far left as possible. Using a complete tree in this case is convenient because this data structure lends itself to being stored in an array, which is very space efficient.
So what does a binary heap array look like? (visual up top) Array, the first element, becomes the root element. Building up the array, for every node Array[i], its parent will be Array[i-1/2], and its left child will be Array[2*i+1]. If there is a right child, it will be Array[2*1 +2].
Bringing the focus back to sorting, the main work in our heap sort is going to be taking the input array and transforming it into a binary heap. In theory, the sort is going to work similarly to selection sort in that it divides the input into sorted and unsorted regions. The main difference is going to be the binary heap structure making the process more time efficient. The heap is going to bring our overall Big O to O(n log n), so in line with merge and quick sorts. Unlike quick sort, the worst-case scenario will still be O(n log n).
Our main tasks are going to be:
Create a max heap out of the initial array.
We are going to take the highest value at the root and swap it with the last element.
Since we know that the last element is in its correct final position, we can remove it from the rest of the heap. We then take the current root item, which may or may not be the remaining highest value, and move it to its correct location in the heap. This method is usually called heapify in a lot of examples.
Rinse & repeat until we have a sorted final array to return.
How about a visual?
And finally, here is our Ruby code for the heap sort. Took some inspiration from this implementation at w3resource.
And there we have it! A fully-functioning heap sort. Buckle up for some buzz words. Heap Sort is an in-place comparison sort that is unstable and non-recursive. It’s Big O is O(n log n). Be sure to say those things when you talk about it to impress people. Keep coding and keep sorting!