Step by Step Example
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
Sort in ascending order
Input: [4, 2, 5, 1, 3, 6]
Output: [1, 2, 3, 4, 5, 6]
First we need to turn our array 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.
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]
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]
Swap array and array
[1, 2, 3, 4, 5, 6]
We have 2 elements that haven’t been sorted yet. We will swap the elements and then our array is in order.
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.
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
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
To analyze the time complexity of heap sort, we break down each step.
- Turn the array into a max heap
- 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).
We are sorting in place, so heap sort takes O(1) space complexity.
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.