Heaps in JavaScript (Part 2)
Will Diep
Posted on October 31, 2020
For this week, we are going to extend what we learned learn week by discussing more immediate fundamentals of Heap:
Bubble Up Part II
Now that we understand how to determine the relationship of elements with the internal heap, we’re ready to finish .bubbleUp().
In a min-heap, we need to ensure that every child is greater in value than its parent. Let’s add an element to the following heap.
console.log(minHeap.heap)
// returns [null, 10, 13, 21, 61, 22, 23, 99]
heap.add(12)
( new_element )
{ parent_element }
[null, 10, 13, 21, {61}, 22, 23, 99, (12)]
Oh no! We’ve violated the min-heap condition because 12‘s parent, 61, is greater than its child, 12.
To fix this, we will exchange the parent and the child elements.
before
[null, 10, 13, 21, {61}, 22, 23, 99, (12)]
SWAP 12 and 61
after
[null, 10, 13, 21, (12), 22, 23, 99, {61}]
12‘s parent is now 13 and it violates the min-heap condition. To fix this, we continue moving upwards swapping parent-child values.
before
[null, 10, {13}, 21, (12), 22, 23, 99, 61]
SWAP 12 and 13
after
[null, 10, (12), 21, {13}, 22, 23, 99, 61]
12‘s parent is now 10 and no longer violates the min-heap condition. We’ve restored the heap!
[null, {10}, (12), 21, 13, 22, 23, 99, 61]
The child, 12, is greater than the parent, 10!
Let’s recap our strategy for .bubbleUp():
Set the current element index to be the last index of heap
While current element is valid and its value is less than its parent's value
Swap the indexes
Update the current element index to be its parent index
class MinHeap {
constructor() {
this.heap = [ null ];
this.size = 0;
}
add(value) {
console.log(`.. adding ${value}`);
this.heap.push(value);
this.size++;
this.bubbleUp();
console.log(`added ${value} to heap`, this.heap);
}
bubbleUp() {
let current = this.size;
while (current > 1 && this.heap[current] < this.heap[getParent(current)]) {
console.log('..', this.heap);
console.log(`.. swap index ${current} with ${getParent(current)}`);
this.swap(current, getParent(current));
current = getParent(current);
}
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
}
const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;
module.exports = MinHeap;
Removing the Min
Min-heaps would be useless if we couldn’t retrieve the minimum value. We’ve gone through a lot of work to maintain that value because we’re going to need it!
Our goal is to efficiently remove the minimum element from the heap. You’ll recall that we always locate the minimum element at index 1 (a placeholder element occupies index 0).
Our internal heap mirrors a binary tree. There’s a delicate balance of parent and child relationships we would ruin by directly removing the minimum.
console.log(minHeap.heap)
// [null, 10, 21, 13, 61, 22, 23, 99]
minHeap.popMin()
// 10
// [null, ???, 21, 13, 61, 22, 23, 99]
We need to remove an element that has no children, in this case, the last element. If we swap the minimum with the last element, we can easily remove the minimum from the end of the list.
[None, (10), 21, 13, 61, 22, 23, {99}]
minHeap.popMin()
SWAP minimum with last
[None, {99}, 21, 13, 61, 22, 23, (10)]
remove minimum
[None, 99, 21, 13, 61, 22, 23]
10
We removed the minimum element with minimal disruption. Unfortunately, our heap is out of shape again with 99 sitting where the minimum element should be. We will solve this in exercises to come…
class MinHeap {
constructor() {
this.heap = [ null ];
this.size = 0;
}
popMin() {
if (this.size === 0) {
return null;
}
console.log(`\n.. Swap ${this.heap[1]} with last element ${this.heap[this.size]}`);
this.swap(1, this.size);
const min = this.heap.pop();
this.size--;
console.log(`.. Removed ${min} from heap`);
console.log('..',this.heap);
return min;
}
add(value) {
console.log(`.. adding ${value}`);
this.heap.push(value);
this.size++;
this.bubbleUp();
console.log(`added ${value} to heap`, this.heap);
}
bubbleUp() {
let current = this.size;
while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
console.log('..', this.heap);
console.log(`.. swap index ${current} with ${getParent(current)}`);
this.swap(current, getParent(current));
current = getParent(current);
}
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
}
const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;
module.exports = MinHeap;
Posted on October 31, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
