Sort Yourself — An Intro to Heapsort
When you need to sort an array, you may run to the fastest solution, even if there’s a risk it’ll take longer than you thought. However, when you absolutely need to get things in order by x amount of time, heap sort is just what you need.
As the name implies, heap sort involves sorting a heap. A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements.
Small note: when structuring a heap, the value of the right child vs left child is not important. The parent element just needs to be greater than its children.
In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i, its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one).
For example, the children of the root element arr[0] will be located in arr[1] and arr[2]. Since the array is representing a complete binary tree, every spot will be filled. This means the children of arr[1] will be in arr[3] and arr[4], the children of arr[2] are in arr[5] and arr[6], and so on.
If the array follows the rules of a heap (meaning the parent’s value is always greater than the value of its children), the root/first element will be the largest value in the array.
On to the sorting!
The heap sort algorithm can only be done an array that has been arranged into a heap. The array below (and it’s accompanied tree visualization) is already a heap.
Since the goal of sorting within an array is to place each element in its correct (sorted) position, you can swap the value of the first element in the unsorted array (the largest) with the value of the last element in the array.
Now the elements, while still in one array, can be considered in two separate sections; sorted and unsorted. The sorted section has begun with the last value in the entire array. When the unsorted section is a heap, the first value can be swapped with the last value in the unsorted section, which adds to the beginning of the sorted section.
However, this means that the unsorted section of the array no longer follows the rules of a heap. What do we do?
Unless the heap has under 3 values, this occurs with every iteration of the heap sort. When the first value in the unsorted section (the largest) is swapped with the last value, the root parent value will no be larger than the value of both children. As such, the first value, in this case 5, will need to be moved down until the rules of a heap are obeyed. This is also known as reheapification downward, which is done by comparing the value of the root/parent with the value of each of its children and swapping to make the unsorted section a heap again. If one or both children are larger than the parent, the parent’s value is exchanged with the larger of the two children.
Swaps will continue (recursively) until the original swapped element (5) is in the correct place for the unsorted section to become a heap.
When the unsorted array is a heap again, you can then place the root value (largest value in the unsorted array) at the end of the unsorted array.
After the swap, the sorted section (shown in gray) will contain both 47 and 50. This continues until the iteration n-1 (n being the total number of elements in the array) is complete. The animation below demonstrates the rest of this heap sort:
Why should I depend on Heap Sort?
While it may not always be the fastest method of sorting, you can count on heap sort not to spiral out of control no matter what you need it to handle. In order to place all the values in their correct (sorted) positions, a heap sort operation needs to be performed on every element in the array except the first (it is already placed in the correct position when the last parent and child node in the unsorted array are swapped) which results in a runtime of O(n). After each heap sort/swap, the new ‘root’ element needs to traverse through the binary tree array, comparing its value until it is in the correct place to again make every parent element greater than its children ( O(log n) ). This altogether results in an average-case runtime of O(n log n). However, due to the way the heap sort algorithm is structured as shown above, the worst case runtime is also O(n log n).
Here is a code representation of a heap sort:
You can find more information about heaps and how they’re built here:
https://www.geeksforgeeks.org/binary-heap/
https://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html
Now get sorting!
