Learning Heap Sort in Javascript

In this week's post I'll be going over how to do a heap sort using javascript. In a past post I've discussed heaps as a data structure. Since this sort utilizes a heap I recommend checking out that first.

Now onto the heap sort. Heap sort works similarly to selection sort in that they both find the maximum element and place it at the end.

Helper Methods

Due the the comparing we're going to be doing between elements it's a good idea to have a method that can easily swap the location of elements. We can easily do this using some fancy ES6 syntax.

We're also going to need a method that turns an array into a max heap. Remember that this means that each node will be greater value than it's children.

The Sort

The function works by taking the input array and turning it into a max heap. From here we swap the location of the root node and the last node, and then we reduce the size of the heap by one, effectively removing the largest value. We then repeat this process until there are no more values in the heap.

Heap sort has a runtime of O(nlogn). This means that a good situation to use a heap sort is when you're want a consistently timed sort (in games) but don't necessarily need the quickest solution every time. Heap sort will always have a O(nlogn) whereas a quick sort is often faster but can potentially be very slow.

Thanks for reading! The code for this post can be found here.