×We're offering Women's Scholarships for applicants to our February class! Details here.
By the end of this chapter, you should be able to:
In addition to binary search trees, there is a similar data structure called a binary heap which shares some characteristics to binary search trees, but is a bit different in its implementation, which makes it a better data structure for some operations, but not others. With binary heaps, there are two common implementations, a max heap (the higher nodes bubble up to the root) and a min heap (the lower nodes bubble up to the root)
A binary heap can be implemented in two different ways, either as a tree or as an array, but let's first define the rules for a binary heap.
Let's take a look at a max-heap:
Notice that the larger values are closer to the root, with the largest value being the root. Remember the order of a heap, everything must be from top to bottom and then left to right so all that matters in terms of the max value is that the parent node is always greater than the child node. This is not like a binary search tree where all values less than a parent node go on the left. With a binary heap we build the data structure starting from the top and going to the bottom and then left to right. If another node were to be inserted, it would be to the left of the node with a values of
Let's take a look at a min-heap:
Notice that the smaller values are closer to the root, with the smallest value being the root. If another node were to be inserted, it would be to the left of
Let's now take a look at how to insert a node into a binary heap. For this example we will be using a max heap. Let's first examine the operations necessary for correctly inserting a node in a max-heap.
Let's now take a look at how to remove a node into a binary heap. For this example we will be using a max heap. While we could remove nodes from anywhere in a heap, removal is commonly done through removing the root node (the highest value in a max heap or the lowest value in a min heap). Here is how it works with a max-heap:
For a parent at index
- its left child will be at index
2n + 1
- its right child will be at index
2n + 2
For a child node at index
- its parent node will be at index
Math.floor( (n-1) / 2 )
Here is what a min-heap with an array representation would look like:
Using the index values in the array, see how the
2n+2 rules apply as well as finding a parent index from a child index. These rules are essential to understand for inserting and deleting when using an array to represent a binary heap.
You can watch an excellent video on an array implementation here
Binary Heaps are commonly used for the following (as well as quite a few other things):
heapsort - Heapsort is a useful in-place (O(1) space complexity) sorting algorithm that has an average performance of O(n log(n)). It requires building a heap and then swapping values to sort. You can read more about heapsort here and see a good visualization here.
priority queue - We previously have seen queues which allow for O(1) insertion and deletion and a more advanced implementation of a queue is one that can re-order itself when a new element is enqueued. The elements in the queue are re-ordered in terms of their priority, which is why this is called a priority queue. Priority queues are easily implemented using min or max heaps to manage the priority and ordering of the queue.
min-max-heap - we have seen min and max heaps, but there is also another data structure called a min-max heap which is a combination of min and max heaps and are frequently used to implement double-ended priority queues. You can read more about them here.
Binary heaps have impressive performance characteristics for deletion and insertion, but they are not as efficient as binary search trees for searching since each node must be visited. The space complexity for a binary heap is O(n) similar to binary search trees.
When you're ready, move on to Binary Heaps Exercises