A binary heap is an interesting and useful data structure based on the concept of binary trees. In this article, we'll introduce this data structure, discuss the core concepts, create an implementation strategy, then show a full code implementation in multiple languages. If you're not familiar with binary trees, please read our introduction to binary trees to ensure you have the required context to move forward.
A heap is a tree with a restriction on how nodes can be arranged. There are two types of heaps: min heaps and max heaps. A max heap is a heap which has the property that for any given node, all decendants of that node have a value less than the node. A min heap has the reverse: all decendants have a value greater than. In both types, the additional restriction gives us certain guarantees about the state of the tree at any given time: the root of the tree will always contain the min/max value. Since they are closely related, we will only discuss max heaps for the remainder of this article.
Complete Binary Trees
A complete binary tree is a tree where all rows above the bottom row are entirely filled, and the bottom row is itself entirely filled or partially filled from the left. In other words, there can be no "gaps" in the bottom row except for one to the right of the last node. The diagram below shows a few example of complete and incomplete binary trees. The orange nodes represent missing nodes which cause the tree to be incomplete.
With this algorithm, large values will "bubble up to the top" as they are added in. The heap structure is not guaranteed to be fully sorted, but larger values will tend to rise to the top, and it is guaranteed that the root will have the largest value at all times.
With this algorithm, once the root node is swapped with the value of the last item, that last item will "bubble down" until it finds its correct position. This guarantees that the new root value will contain the largest of the remaining values.
Care must be taken when calculating these indices, as a potential "off by one" error can easily appear. An interesting note: if heaps provided the ability to iterate over all nodes: looping through each item in the array, in order, would be equivalent to performing a breadth-first search on the heap tree.
Heaps provide fast performance for insertions and removals and always guarantee the value removed is the min/max value in the structure.
|Operation||Worst Case Complexity||Notes|
|Find Max Value||Max heap structure guarantees the max value will always be the root node.|
|Insert||The upper bound on the number of operations is related to the tree's height.|
|Remove||The upper bound on the number of operations is related to the tree's height.|
The implementation below brings everything discussed above together into a "CustomMaxHeap" class: