Binary Heaps and Sorting

Binary heaps are pretty rad. If you're not exactly sure what a binary heap is, then maybe you're more familiar with its brother, the binary search tree. Like the binary search tree, binary heaps are visualized as a tree structure with a root node where every node branching off of the root node can have up to two child nodes.

The difference is that in binary search trees the entire tree is ordered from smallest to largest. On the other hand, Binary heaps only enforces the ordering between a parent node and its children. You can play with binary heaps here to get a better feel for what I will be laying out in the next few paragraphs.

As you insert nodes into the binary heap, the nodes on the tree are filled out level by level from left to right. That is, you cannot increase the depth of the tree without first completely filling up all the available spots at the current deepest level. Each time a node is inserted, it is compared with it's parent node and may switch positions with it. If we are dealing with a min binary heap, the nodes will switch if the child node's value is greater than the parents. The reverse is true for max binary heaps. A newly inserted node will keep moving up the tree towards the root node until the comparison function shows that its parent node is smaller than it (in the case of a min binary heap).

Binary heaps can be easily implemented using an array structure due to the fact that there are simple equations you can use to find which element in the array is a parent or child to any other element in the array.

var parentIndex = Math.floor( (nodeIndex - 1) / 2 ); will give you the parent index if you provide it with the index of a child node. var childrenIndices = [nodeIndex * 2 + 1, nodeIndex * 2 + 2]; will provide an array of the children (if they exist) of any parent node. So for example, an array that looks like [0,1,2,3,4,5,6,7,8,9], index 0 is the root node and its child nodes are index 1 and 2. The child nodes of index 3 are 7 and 8. Index 9 is an only child which points to index 4 as it's parent.

Things get slightly more interesting when we implement a remove root function. Because we want to maintain the tree's current structure, when we remove the root from the tree we have to replace it with something. We can do this by switching the positions of the root node with the node at the end of the array. We can then safely pop off the last node in the array to get the root without compromising the structure of the tree.

However, we're not done yet. The tree still has to be reordered if any parent nodes are greater in value than either of their child nodes. Any time we bring a node from the end of the array to the root, it is almost certain that this will be the case. Similar to what we did with insertion, the new root node will travel down the tree switching places with it's lowest valued child until either both of its children have higher values than it, or it gets back down to the end of the tree (not necessarily the end of the array though). The intersting thing that happens here is that the root node that is in place when all of this switching is done is always going to be the smallest value in the set.

Your mind gets blown when you realize that this is actually a powerful sorting algorithm. All you have to do is keep removing the root and push them into an array in the order they came out. What you get is an array of values in acending order. You can do for a max binary heap to get the values in decending order. This sorting algorithem we've described is called heap sort. Heap sort is a powerful algoritim only having a worst case time complexity of O(n log n) and O(1) space complexity while sorting. It's main downfall is that it does not give you back a stable sort so it is only useful when that is not an issue.