This post is one in a series of stuff formally trained programmers know – the rest of the series can be found in the series index.
Continuing on with more tree-based data structures, we get to the heap. If we look back at the BST and Red/Black those trees ended up with the most average/middle value at the root node so that nodes which were smaller were on the left and larger nodes were on the right, the heap changes that.
There are actually two heaps, a minimum and maximum value heap, but there are very similar. The key aspects to know about either heap are
- It is a binary tree. This is important for insertion and deletion and ensures the depth of the tree doesn’t grow out too far from the root node.
- In a minimum heap, the root node is the SMALLEST value in the tree.
- In a minimum heap, any node should be smaller than all of its’ children
- In a maximum heap, the root node is the LARGEST value in the tree
- In a maximum heap, any node should be larger than all of its children
The advantage of a heap is as an implementation of a Queue where you can control the order items appear in the queue rather than just relying on insertion order.
Let’s have a look at what these will look like when we have the following dataset: 45, 42, 56, 78, 99, 30
| Step | Minimum Heap | Maximum Heap | ||
|---|---|---|---|---|
| 1 | We add 45 as the root node | We add 45 as the root node | ||
| 2 | We add 42 as the first child, but it is smaller, so we will swap it with the root node |  {width=100}  {width=100} |
We add 42 add as the first child node |  {width=100} |
| 3 | We add 56 as the second child node |  {width=100} |
We add 56 as the second child node; it is larger than its parent so we swap them. |  {width=100}  {width=100} |
| 4 | We add 78 as a child of 45 |  {width=100} |
We add 78 as a child of 42, though it is larger so it must be swapped. 78 is now a child of 56, which still wrong so we need to swap them too. |  {width=100}  {width=100}  {width=100} |
| 5 | We add 99 as a child of 45 |  {width=100} |
We add 99 as a child of 56. 99 is larger, so we then swap 99 and 56. 99 is still larger than 78, so we need to swap those nodes too |  {width=100}  {width=100}  {width=100} |
| 6 | Next we add 30 under 56. It is smaller than 56 so it must be swapped. Once swapped, its parent 42 is also larger so they need to swapped too. |  {width=100}  {width=100}  {width=100} |
Last we add 30 to under 45. |  {width=100} |
Implementations
Java has a built-in implementation with the PriorityQueue and, unfortunately, .NET and JavaScript lacks an out of the box option.