Note: Check out the entire supplemental source code for this blog series.
Binary Heaps
Heaps store nodes in a tree structure where nodes are stored in a hierarchy. That is each node has exactly one parent (except for the root). A binary heap stores nodes in a binary tree structure which is a tree where each node has at most two child nodes.
Because each node will have two children, in a complete binary tree each row or layer of the tree will hold twice as many nodes as the layer before it. Therefore, the height of the tree grows logarithmically.
Implementation
There are many ways to implement a binary tree. For this implementation, we will use an array with some fancy footwork to achieve a concise solution. We will store the nodes in an array, from top to bottom, left to right like this:
Using this representation, the first element of the array will be the root node and the two children of a node at index i will be stored at 2i + 1 (left child) and 2i + 2 (right child).
One benefit of a heap is that it can be easily structured on any property of a node that is comparable. Here structured means that parent nodes’ values will always satisfy a comparison condition when compared to their children’s values. For example, this implementation includes both a min and a max binary heap. The min binary heap ensures that parent nodes will always have a lesser value than their children. While a max binary heap ensures that parent nodes will always have a greater value than their children. This means that in a min binary heap, the root node will always be the minimum. And, for a max binary heap, the root node will always be the maximum. This is how we can achieve Θ(1) time for either minimum or maximum.
Insertion
When a binary heap is structured, care must be taken on insertion to maintain the structure of the heap. When a new node is inserted, it is added as the last node in the tree, at the very bottom. It then floats up to the top, repeatedly swapping its position with its parent if its relationship with its parent doesn’t satisfy the structure condition. Eventually, the structure condition will be met, and the insertion will be complete. In the worst case this will take Θ(lgn) because the height of the tree and thus the number of comparisons and swaps will be lgn.
Deletion
Likewise, deletion must be implemented in a way to maintain the structure of the heap. When a node is deleted, the last remaining node in the heap is placed at the position of the deleted node. Then, the node floats down to the bottom, by repeated swapping its position with one of its two children if the structure condition doesn’t hold. Just like insertion, after a maximum of lgn swaps, the structure condition will eventually be met, and the deletion will be complete.
Pros
- Unlike the previous data structures we’ve covered, binary heaps can be structured to have a worst-case runtime of Θ(1) for the minimum or maximum operation.
Cons
Unlike linked lists, if the underlying array is full and needs to be rebuilt, the insertion will take Θ(n) time.
Unlike linked lists, deletion takes Θ(lgn) time.
Unlike hash tables, searching takes Θ(n) time.
Use Cases
- Because binary heaps can be structured to have Θ(1) worst-case minimum or maximum operations, they will be very performant in situations when the minimum or maximum element will need to be maintained and repeatedly accessed. Specifically, binary heaps would be well suited for a priority queue.
Binary Heaps in C#
- As of the time of this writing, C# does not provide an implementation of the binary heap.
Performance
| Name | Average Case Time Complexity | Worst Case Time Complexity |
|---|---|---|
| Insert | Θ(lgn) | Θ(n) |
| Delete | Θ(lgn) | Θ(lgn) |
| Search | Θ(n) | Θ(n) |
| Minimum | Θ(1) | Θ(1) |
| Maximum | Θ(1) | Θ(1) |