Binary heaps are binary trees that are sorted in such a way that the parent leaf is either greater or lesser than both of its child nodes. When the root node is the greatest and each parent is greater than its children, then it’s a max heap. In the opposite scenario, we have a min heap. When presented with an array, we simply line up each element in the array from left to right, top to bottom in a binary tree format.
For example, the array [1, 3, 6, 5, 9, 8] would correspond to the following binary tree, sorted as a min heap:
When presented with the problem of turning an array into a max heap, my initial thought was “Why don’t you just sort the array from greatest to least? Surely that will satisfy the binary condition without any fancy schmancy algorithms or recursion.”
Turns out, it doesn’t.
In order to solve this problem, you need to individually check each node and guarantee it follows the heap rule (that is, whether it is greater or lesser than its children if it’s, respectively, max or min heap).
Confused out of my mind, I consulted MIT Open Courseware’s lecture on the subject, and, after that, I was even more confused. Just to get the slightest idea of what I was dealing with, I decided to get a solution down in Xcode, whether it was great or faulty, and scripted out something like this:
1. Check every node in the tree if it follows the rule. If it doesn’t, switch the node with its parent.
2. Check the tree if each node follows the rule. If not, go back to step 1. If yes, then you win!
From a computational standpoint, the errors are fairly obvious. You’d have to check each node individually over and over again until you found the mistake, and then, you’d have to check the entire tree over again.
What might make more sense would be to check each node if it follows the rule and, if it doesn’t, check the parents recursively until you climb to the top of the tree, checking for errors along the way. This will rearrange the nodes in such a way that it fixed more errors more efficiently. My original solution does not “bubble-up” through the entire tree.
I’ll have to fix this sometime in the future. In the meantime, I’m still working on breadth-first searches, Dijkstra’s theorem, and sorting by reversals. Hopefully those will be the subjects I touch upon in the future as I get my gears in shape.
My solution to Building a Heap can be found at https://github.com/HussainAther/rosalind/HEA.py