May 13, 2019 ·

# 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);
}
}
``````