In the last blog we were introduced to a minimum binary heap, potential uses, such as a queue and the basics of how to build one. In this blog we will be going over how to remove the lowest value from our heap. Just as a quick refresher you might want to look over the last blog here, https://skabe.medium.com/minimum-binary-heap-part-1-insert-a5ac99d22f10
So far our heap looks like so
class MinimumHeap{ constructor(){
this.values = []
} insert(val){
this.values.push(val)
if(this.values.length > 1) this.bubbleUp(this.values.length - 1)
} bubbleUp(idx){
parent = Math.floor((idx - 1) / 2)
if(this.values[idx] < this.values[parent]){
[this.values[idx], this.values[parent]] =
[this.values[parent], this.values[idx]]
this.bubbleUp(parent)
}}
Our heap works by inserting our new value into the array at the highest index and comparing that value with the value of its parent. Our lowest value will always be the root of the tree, kept at the 0 index. We could use the shift method on our ‘values’ array to remove our lowest value but this would come with a few issues. First, removing from the front of the array will put unnecessary strain on our function since this will cause our array to reassign indexes to each value in the array. Secondly, the way our insert is set up, we aren’t guaranteed that our left child is a lower value than it’s sibling. This means we would have to reorder our tree. To do this more efficiently we can implement something that is almost the inverse of our insert/bubbleUp combo, remove/cascadeDown.
First let’s work on removing from the front of our array.
removeMin(){
if(this.values.length === 0) return undefined
if(this.values.length === 1) return this.values.pop() [this.values[0], this.values[this.values.length - 1]] =[this.values[this.values.length - 1], this.values[0]] let oldMin = this.values.pop()
return oldMin
}
In the first line in our removeMin function, we are checking if the array is empty, if so we will return undefined. In the second line we’re checking if the the array only has one element, in which case we can easily just use pop(). The third line, which on my screen is too long to actually be just one line, is swapping the first element (lowest val) with the last element (last child in our array). Then we are popping the last element from our array.
[1, 2, 4, 3, 5, 12, 9, 7] [7, 2, 4, 3, 5, 12, 9, 1]swap, then pop[7, 2, 4, 3, 5, 12, 9] => oldMin = 1
We can’t just stop here though. As you can see 7 is the root of our heap and therefore our minimum heap is no longer valid. We will now do the inverse of the bubbleUp function we build in the last blog.
function cascadeDown(idx){
let leftChild = (idx * 2) + 1
let rightChild = (idx * 2) + 2
let min if(!this.values[leftChild]) return true
else if(!this.values[rightChild) min = leftChild
else if(this.values[leftChild] <= this.values[rightChild]){
min = leftChild
}
else{
min = rightChild
} if(this.values[idx] > this.values[min]){
[this.values[idx], this.values[min]] =[this.values[min], this.values[idx]]
this.cascadeDown(min)
}
}
This looks like a lot to unpack but I promise it’s not as complicated as it looks. Our cascadeDown function is taking the argument of an index, which in our remove function we will call on the 0 index in our values array. In the first three lines here, we are setting variables to the two children of our index and also establishing a ‘min’ variable. Following our variable declarations, the first chunk of conditionals are trying to figure out which of our two children is the lower value. The first ‘if’ is checking to see if our current index has children at all. This first ‘if’ is also serving as a way to break out of our recurring function if we get to an index with no children. The following ‘else if’ is checking if it has a right child, if not the left child is set to the ‘min’ variable. The following two conditionals are there to establish which child is the lower value if there are two children.
The next conditional is checking if our current index is a higher value than its lowest valued child. If it is then it will swap those two in our array and call the cascadeDown function on the new position of our original value. To make it easier to visualize lets walk through what will happen when we call it.
class MinimumHeap{constructor(){
this.values = []
}insert(val){
this.values.push(val)
if(this.values.length > 1) this.bubbleUp(this.values.length - 1)
}bubbleUp(idx){
parent = Math.floor((idx - 1) / 2)
if(this.values[idx] < this.values[parent]){
[this.values[idx], this.values[parent]] =
[this.values[parent], this.values[idx]]
this.bubbleUp(parent)
}removeMin(){
if(this.values.length === 0) return undefined
if(this.values.length === 1) return this.values.pop() [this.values[0], this.values[this.values.length - 1]] =[this.values[this.values.length - 1], this.values[0]] let oldMin = this.values.pop()
cascadeDown(0)
return oldMin
}cascadeDown(idx){
let leftChild = (idx * 2) + 1
let rightChild = (idx * 2) + 2
let min if(!this.values[leftChild]) return true
else if(!this.values[rightChild) min = leftChild
else if(this.values[leftChild] <= this.values[rightChild]){
min = leftChild
}
else{
min = rightChild
} if(this.values[idx] > this.values[min]){
[this.values[idx], this.values[min]] =[this.values[min], this.values[idx]]
this.cascadeDown(min)
}
}}
*Our current current MinimumHeap with ‘cascadeDown’ added to ‘removeMin()’
heap.values = [1, 2, 4, 3, 5, 12, 9, 7][7, 2, 4, 3, 5, 12, 9, 1]*Lowest value swapped with last element in index[7, 2, 4, 3, 5, 12, 9]*Lowest value popped from array, stored as oldMin
oldMin = 1cascadeDown called with index of 0
*p = parent or current value
*l = left child
*r = right child[7, 2, 4, 3, 5, 12, 9]
p l r*Lowest value child or 'min' established as l => swap[2, 7, 4, 3, 5, 12, 9]
p l r*min = l => swap[2, 3, 4, 7, 5, 12, 9]
p*No children, heap in order
There we have it, a working Minimum Heap!
