Heaps in JavaScript (Part 3)
Will Diep
Posted on November 7, 2020
For our final introduction to what and how to use heaps in JavaScript, we are going to dive into how to "heapify' using Object Orientation with Classes.
Heapify I
We’ve retrieved the minimum element but left our MinHeap in disarray. There’s no reason to get discouraged; we’ve handled this type of problem before, and we can get our MinHeap back in shape!
We’ll define a method, .heapify(), which performs a similar role to .bubbleUp(), except now we’re moving down the tree instead of up. The current element is a parent that can have either a left child or two children, but not just a right child.
We have written a helper method, .canSwap(), to return true if swapping can occur for either child and false otherwise:
canSwap(current, leftChild, rightChild) {
// Check that one of the possible swap conditions exists
return (this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
|| this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
);
}
To maintain the min-heap condition, the parent value has to be less than both its child values. To see if a swap is necessary, starting with the left child, we first check that the child exists and then whether the min-heap condition is broken, i.e. the current element has a value greater than that child’s value. If the left child does not break the min-heap condition, the same check is performed on the right child.
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(`.. swap ${this.heap[current]} with parent ${this.heap[getParent(current)]}`);
this.swap(current, getParent(current));
console.log('..', this.heap);
current = getParent(current);
}
}
heapify() {
let current = 1;
let leftChild = getLeft(current);
let rightChild = getRight(current);
while (this.canSwap(current, leftChild, rightChild)) {
leftChild = getLeft(current);
rightChild = getRight(current);
}
}
exists(index) {
return index <= this.size;
}
canSwap(current, leftChild, rightChild) {
// Check that one of the possible swap conditions exists
return (
this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
|| this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
);
}
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;
Heapify II
In .bubbleUp(), we were always comparing our element with its parent. In .heapify(), we have potentially two options: the left child and the right child.
Which should we choose? We’ll use an example to think it through. Imagine we have a heap with four elements:
console.log(minHeap.heap)
// [null, 21, 36, 58, 42]
minHeap.popMin()
// 21
// [null, 42, 36, 58]
// Should we swap 42 with 36 or 58?
We want to swap with the smaller of the two children, otherwise, we wouldn’t maintain our heap condition
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);
this.heapify();
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(`.. swap ${this.heap[current]} with parent ${this.heap[getParent(current)]}`);
this.swap(current, getParent(current));
console.log('..', this.heap);
current = getParent(current);
}
}
heapify() {
let current = 1;
let leftChild = getLeft(current);
let rightChild = getRight(current);
while (this.canSwap(current, leftChild, rightChild)) {
while (this.canSwap(current, leftChild, rightChild)) {
if (this.exists(leftChild) && this.exists(rightChild)) {
if (this.heap[leftChild] < this.heap[rightChild]) {
this.swap(current, leftChild);
current = leftChild;
} else {
this.swap(current, rightChild);
current = rightChild;
}
} else {
this.swap(current, leftChild);
current = leftChild;
}
leftChild = getLeft(current);
rightChild = getRight(current);
}
leftChild = getLeft(current);
rightChild = getRight(current);
}
}
exists(index) {
return index <= this.size;
}
canSwap(current, leftChild, rightChild) {
// Check that one of the possible swap conditions exists
return (
this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
|| this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
);
}
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;
Review
This is how to implement a min-heap in JavaScript, and that’s no small feat (although it could efficiently track the smallest feat).
To recap: MinHeap tracks the minimum element as the element at index 1 within an internal Javascript array.
When adding elements, we use .bubbleUp() to compare the new element with its parent, making swaps if it violates the heap condition: children must be greater than their parents.
When removing the minimum element, we swap it with the last element in the heap. Then we use .heapify() to compare the new root with its children, swapping with the smaller child if necessary.
Heaps are useful because they’re efficient in maintaining their heap condition. Building a heap using elements that decrease in value would ensure that we continually violate the heap condition. How many swaps would that cause?
Posted on November 7, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
