Data Structures: Binary Heap
A heap is a specific type of tree. The general structure of a binary heap is similar to our binary tree, but a few new rules apply. We will discuss max-heaps, min-heaps, and priority queues.
A max binary heap (first photo) is a tree where the parent node is always larger than the child nodes. In a min binary heap (second photo), the opposite is true.
Max binary heap
Min binary heap
Binary heaps also need to stay as compact as possible. This means it fills from left to right and does not proceed to the next level deeper until the current level is filled. The only rule in regards to the organization is that the children must be smaller than the parent (max heap) or larger than the parent (min heap).
The simplest way to create a binary heap is by utilizing an array. I’m sure you’re thinking that looking at the photos above, there isn’t a way to use an array for this. However, using a simple mathematical relationship it is quite easy.
By simply drawing the tree a bit differently, it is easier to see the relationship. This binary heap would be represented by
[2, 18, 4, 22, 98, 7]Here is the relationship we are looking at: any index of an array is defined as ’n’. The left child of ’n’ is present at ‘2n + 1’ and the right child is at ‘2n + 2’. To find a parent, the relationship is ‘floor((n-1) / 2)’. That’s it!
Get jesse kovash’s stories in your inbox
Join Medium for free to get updates from this writer.
Time to get started. We can start by creating a MaxBinaryHeap class.
Class
Inside the MaxBinaryHeap class, the constructor takes no arguments and contains an empty array.
Next, we are going to need some methods so we can insert, as well as extract the largest value.
Insert
We are going to start by simply pushing the value to the end of the array. Next, we need to ‘bubble’ this value to find its position. A while loop will help us traverse the MaxBinaryHeap. On each iteration, we need to check a few things. First, we need to verify that our current value is greater than its parent value. If so, we need to bubble the value by performing a swap between the parent and child values. Second, if the current value happens to be less we have met our while loop termination condition and the value is in its correct position.
ExtractMax
To extract the max value we need to use some different logic. We first need to save the first value (the max value), replace the first value with the last value, and pop the last value. Now we need to take our smallest value which happens to be at index 0, and ‘sink’ it downwards to find its position. Inside of our while loop, we create a ‘swap’ variable that allows us to track if a swap should be made. We simply check if the left child is greater than the current value we need to set the ‘swap’ variable to the index of the left child. One more check is required while checking the right child. If the left child was not greater than the current value, ‘swap’ will still be null. In this case, if the right child is less than the current value, we can simply set ‘swap’ to equal the right child index. However, if the left child was less than the current value ‘swap’ is not null. In this case, we only want to change the value of ‘swap’ if the right child is greater than the current value and the left child. Don’t forget to swap the values at the end of the loop if ‘swap’ is true, otherwise you can simply break since the current value is in its correct position.
The examples above are to create a max binary heap. To create a min binary heap all you need to do is change the comparison signs from > to <.
The next project will be to use our binary heap and tree knowledge to create a priority queue.
