Learning Binary Heaps

Up until this week, the only heaps I was familiar with were the heaps of trash that are a mainstay of NYC streets. Thankfully this week of studying data structures has shown me that not all heaps are hot garbage. In this article, I will be reviewing what I have learned so far about binary heaps as well as how to construct and interact with them. A lot of the images in this article are from my repl, where I constructed a Max Binary Heap and wrote a few class methods to make it functional. I also have some notes in there that will cover much of this article. I hope that both can be helpful to anyone who is interested on gaining a basic understanding of how binary heaps work.

Heaps are a type of tree. They are a lot like Binary Search Trees, but have their own unique logic, rules, and use cases. If you are not familiar with Binary Search Trees(BST), please check out my articles on BSTs and Tree Traversal. Just like in a BST, each node in a binary heap has at most two children(hence them sharing the binary in their name).

However, the rules around the order of nodes is very different. There are two main types of binary heaps, Max Binary Heaps(Max Heap), and Min Binary Heaps(Min Heap). In a Max Heap, each node’s children must have a lower value than their parents. This means that the root node will always have the highest value in the heap. In a Min Heap, the opposite is true. The root node always has the lowest value, and each child node must have a greater value than its parent. Another difference between binary heaps and BSTs aside from the rules I just outlined is that there is no inherent left to right order ascending order for the value of nodes. You can not infer anything about the value of a node’s sibling other than it is also lesser or greater than their parent, depending on if it is a Max Heap or a Min Heap.

What may be the most important between a binary heap and a BST is that the left child node will always be assigned before the right one, and each node must have two children before another level can be added to the heap. This is a stark departure from BSTs, where one could theoretically keep adding nodes to only the left side or the right side, making it look more like a linked list. This difference is essential to a lot of the logic that you will see in my code screenshots below. We are able to construct a heap using an array because of this difference, since with a little bit of math we can figure out the index of a parent node based on it’s child’s index. Given an index of ‘x’, we can call Math.floor of (x — 1)/2. If x is the left child, it will divide evenly by 2. If x is the right child, it will be a float, such as 2.5, and then we can round it down.

Below are some screenshots of the Max Heap that I constructed on replit. This heap is capable of adding a new node or removing the root, and re-organizing the heap. It requires very little set up, since the Heap itself just needs an array of node values to work.

I hope that this has been informative and interesting! Next time, I will be writing about priority queues, which also use heaps.