How to implement Heap data structure in JavaScript?
Let's start by creating the structure of the BinaryHeap class:
class BinaryHeap {
constructor(comparator = (a, b) => {
return (a < b) ? -1 : (a === b ? 0 : 1);
}) {
this.heap = [];
this.comparator = comparator;
}
size() {
return this.heap.length;
}
This heap is default to min heap which you can tell by comparator parameter. In order to customize it to max heap. We need to provide our own comparator, which is something like this. (a, b) => a > b).
To access the nodes of a binary tree using an array, we need the following methods.
getLeftIndex(index) {
return 2 * index + 1;
}
getRightIndex(index) {
return 2 * index + 2;
}
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
We can perform three main operations in a heap data structure:
insert(value): This method inserts a new value into the heap. It returns true if the value was successfully inserted and false otherwise.
extract(): This method removes the minimum value (min heap) or the maximum value (max heap) and returns it.
peak(): This method returns the minimum value (min heap) or maximum value (max heap) without removing it.
Inserting a value into the heap
insert(data) {
if (data === undefined || data === null) {
return false;
}
this.heap.push(data);
this.bubbleUp(this.heap.length - 1);
return true;
}
bubbleUp(index) {
while (index > 0) {
let curr = this.heap[index];
let parentIndex = this.getParentIndex(index);
let parent = this.heap[parentIndex];
let compare = this.comparator(parent, curr);
if (compare < 0 || compare === 0) {
break;
}
this.swap(index, parentIndex);
index = parentIndex;
}
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
Finding the minimum or the maximum value
peak() {
return this.size() > 0 ? this.heap[0] : undefined;
}
Extracting the minimum or the maximum value
extract() {
if (this.size() === 0) {
return undefined;
}
if (this.size() === 1) {
return this.heap.shift();
}
const value = this.heap[0];
this.heap[0] = this.heap.pop();
this.sinkDown(0);
return value;
}
sinkDown(currIndex) {
let left = this.getLeftIndex(currIndex);
let right = this.getRightIndex(currIndex);
let parentIndex = currIndex;
if (left < this.size() && this.comparator(this.heap[left], this.heap[parentIndex]) < 0) {
parentIndex = left;
}
if (right < this.size() && this.comparator(this.heap[right], this.heap[parentIndex]) < 0) {
parentIndex = right;
}
if (parentIndex !== currIndex) {
this.swap(parentIndex, currIndex);
this.sinkDown(parentIndex);
}
}
