SFTPK: Heap
This post is one in a series of topics 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 trees, 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 they 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 | We add 42 as the first child node |
  |  | |
| 3 | We add 56 as the second child node | We add 56 as the second child node; it is larger than its parent, so we swap them. |
 |   | |
| 4 | We add 78 as a child of 45 | 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 is still wrong, so we need to swap them too. |
 |    | |
| 5 | We add 99 as a child of 45 | We add 99 as a child of 56. 99 is larger, so we swap 99 and 56. 99 is still larger than 78, so we swap those nodes too. |
 |    | |
| 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 be swapped too. | Last, we add 30 under 45. |
   |  |
Implementations
Java has a built-in implementation with the PriorityQueue, and unfortunately, .NET and JavaScript lack an out-of-the-box option.