Implementing Heap Sort in JavaScript

Photo by Volodymyr Hryshchenko on Unsplash

Last week I wrote about implementing a max heap in JavaScript, now we’re going to put that knowledge to the test and write a heap sort algorithm. Understanding the implementation, and time and space complexities of a max heap will make understanding the heap sort algorithm quite simple.

Step by Step Example

The Process

We know in a max heap, the largest element is stored at the root. So these will be the steps of heap sort:

• Move the element at index 0 to the end of the array
• Re-heapify the array, excluding the last element
• Continue this process of swapping and re-heapifying each time excluding the elements that you’ve moved to the end of the array

Expected result

Sort in ascending order
Input: [4, 2, 5, 1, 3, 6]
Output: [1, 2, 3, 4, 5, 6]

First Step

First we need to turn our array into a max heap.

The array after turning it into a max heap

Now that our array is a max heap, we need to start swapping elements.

First we will swap the element at index 0 and index 5.

So the array is now: [4, 3, 5, 1, 2, 6]

Then, we need to re-heapify all of the elements except for the one at index 5.

The array with the greatest element in place

Second Step

We need to swap the elements at index 0 and index 4 and then re-heapify again.

After swap: [2, 3, 4, 1, 5, 6]

Then, re-heapify…

The array with the last 2 elements in place

Third Step

We need to swap the element at index 0 with the element at index 4.

Array before re-heapifying: [1, 3, 2, 4, 5, 6]

After re-heapifying…

Array with last 3 elements in place

Fourth Step

Swap array[0] and array[2]
[1, 2, 3, 4, 5, 6]

Re-heapify

Array with last 4 elements in place

Final Steps

We have 2 elements that haven’t been sorted yet. We will swap the elements and then our array is in order.

Code

I won’t spend too much time talking about functions that are based off of things I went over in my last blog post. The main difference is that these won’t be class methods, however the concepts behind them are the same.

A swap function, as we will be doing a lot of swapping.

Now we will make a heapify function. This will be the equivalent to the heapifyDown method from my last blog.

One difference is we need to pass in a length property, as when we use this with our heapSort function, we will be passing in the last index of the unsorted section of our array. We don’t want it to take the maximum value that we just put at the end of our array, and put it back at index 0. This is why our if statements check to make sure the children aren’t beyond the length.

Finally, our heapSort function.

The code from lines 3 to 5, acts as our buildHeap method from the last blog. From there it is just like the step by step example. Swapping the first element with the last element in the unsorted section, and then re-heapifying the unsorted section. It is similar to selection sort.

Time Complexity, Space Complexity, and Stability

Time Complexity

To analyze the time complexity of heap sort, we break down each step.

1. Turn the array into a max heap
2. Iterate through the array, on each iteration:
   a. Swap elements
   b. Re-heapify the array

From my last blog we know that to turn an array into a max heap takes O(n) time, and that heapify takes O(log n) time. Swapping takes constant, or O(1) time.

So we have:
O(n) + O(n * (1 * log n))

We know we don’t care about constants, which then leaves us with:
O(n + n log n)

We only care about the dominant term of the function, so our time complexity is O(n log n).

Space Complexity

We are sorting in place, so heap sort takes O(1) space complexity.

Stability

Heap sort is unstable. If you need a reminder on what that means you can review my blog about implementing insertion sort in JavaScript, where I go over it in more detail.

In Conclusion…

Heap sort isn’t see very often in the real world, but it could be useful for embedded systems where you’re working with little memory, because it takes O(1) space in memory. In addition to that, its best, worst, and average time complexity are all O(n log n), so you don’t run the risk of it taking O(n²) like with quick sort. However, heap sort isn’t as fast as quick sort on large arrays, and offers no advantage when handling partially/mostly sorted arrays. Introsort is a sorting algorithm which seeks to combine the advantages of quick sort and heap sort. The code used in this blog can be found in this GitHub repository.