Heap Sort
Hello! As part of what I think is probably the classic “start getting to the end of Flatiron program and realize you don’t know enough basic CS concepts to pass an interview” stage of learning, I am going to talk about Heap Sort.
First of all, it’s similar to Selection Sort. I don’t know what that is yet, but I will by the time I actually present this blogpost. The basic concept behind heap sort is that you’re finding the maximum element then placing the maximum element at the end.
It’s worth noting that the time-complexity of HeapSort is O(nlogn). Also, I will be relying heavily on GeeksforGeeks in this post.
Okay. So. First thing that happens is that you take your input information and make a binary tree. So, for input [4, 10, 3, 5, 1], the binary tree would look like this:
This is built because (and I’m speculating based on evidence here) that you start with a node, do each of its children, then do the children on one of its children before moving to the next. So if there had been a sixth number, it would have gone to the left of the three and a seventh number would have gone on the right of the three.
Anyway. At this point you make sure that the parent nodes are sorted from highest to lowest starting at the head node. In this case, you would switch the 10 and the 4. At this point, all parent nodes are larger than its children (10 is larger than 5 and 3, 5 is larger than 4 and 1. This is an example of what is called a “Max Heap.” (Keep an eye on the array at the top — its indices are changing places with their location on the binary tree.)
Next, to continue the heap sort, you switch the head node with the last node. In this case, the “10” with the “1”, and then remove the last node (now 10). This results in a tree which looks like this:
As you can see, this is no longer a Max Heap. We need to return to that state. So we compare the five with the one and switch them. Then, we compare the 3 with the 5 that is now the head node and leave that because 5 is larger than 3. However, the 1 has a child node of 4, so we switch those.
We then once again switch the head node (5) with the final node (1) and, you know… rinse and repeat. 1 would now be the head node again, so we’d switch it with 4. 3 is smaller than 4, so the right branch is left alone. We then switch the head(4) back with the last node (1) and remove the last node (4). We then compare the head node(1) with its only remaining child (3). The 3 is larger, so we switch it. Then we have a Max Heap and so we switch the head(3) node with the smallest(1).
This would leave us with only one node — a 1. So we’re done! We have successfully walked through a heap sort.
Below I’ve added the whole video (since it’s hard to follow in just writing).
You can also view more information at: https://www.geeksforgeeks.org/heap-sort/
Thanks!
