Here’s what I’ve learned about the heap data structure.
The invariant of the min/max heap is this: when represented in a binary tree, the parent node’s value is always smaller/bigger than or equal to its children. The root is always the smallest/biggest value of the heap when represented as a binary tree.
The two most important operations supported by heaps are insert() and extractMin()/extractMax().
In this post, we will focus on the implementation of the min heap. The max heap can easily be implemented by changing some constant factors.
We will write our heap implementation, taking advantage of the ES6 Class syntax, and export it for reusability.
Let’s start with the constructor.
class MinHeap {
constructor() {
this.values = [];
}
}
export default MinHeap;And just like that, we complete the first building block of the heap with an empty array. Why did we discuss the heap as a binary tree before, but now represent it with an empty array?
It’s because parent-child relationships supporting the heap can be easily translated to an array. Here are the details (assuming a zero-based index array):
For every index greater than 0 (excluding the root), the parent index of the child index i is either ⌊(i – 1) / 2⌋ if i modulo 2 is not equal to 0 (usually the left child) or (i – 2) / 2 if i modulo 2 is equal to 0 (usually the right child).
Equivalently, the left child index and the right child index of the parent index i are 2i + 1 and 2i + 2, respectively.
With these parent-child relationships, we can easily translate the heap binary tree into an array, without worrying about the occupied space when dealing with multiple pointers.
Now, let’s shift gears and discuss the insert() operation of the heap.
Let’s dive right into the implementation.
class MinHeap {
constructor() {
this.values = [];
}
insert(value) {
this.values.push(value);
const bubbleUp = (index, arr) => {
if (index <= 0) return;
let { distance: currentDistance } = array[index];
let parentIndex =
index % 2 === 0 ? (index - 2) / 2 : Math.floor((index - 1) / 2);
let { distance: parentDistance } = array[parentIndex];
if (currentDistance < parentDistance) {
this._swap(array, index, parentIndex);
}
bubbleUp(parentIndex, array);
};
bubbleUp(this.values.length - 1, this.values);
return this;
}
_swap(arr, index1, index2) {
let temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
export default MinHeap;Initially, we take a naive approach and simply push the new value to the end of the heap array.
Subsequently, we recursively compare the new value with its parent, utilizing the parent-child relationships discussed earlier, and bubble it up (swap its value with the parent) to its correct position in the array. This process is implemented as the bubbleUp() expression in the code.
Since the value was appended to the end of the array, we execute the bubbleUp() method, starting at the final index of the array, and ultimately return the array when the bubbleUp() method halts.
The _swap() method is a straightforward function to swap values between two array indexes.
The running time of the insert() operation is O(log2n).
Moving on, we will implement another vital method for a heap, extractMin().
Once again, let’s delve into the implementation, and we’ll discuss the explanation later.
class MinHeap {
constructor() {
this.values = [];
}
insert(value) {
this.values.push(value);
const bubbleUp = (index, arr) => {
if (index <= 0) return;
let { distance: currentDistance } = array[index];
let parentIndex =
index % 2 === 0 ? (index - 2) / 2 : Math.floor((index - 1) / 2);
let { distance: parentDistance } = array[parentIndex];
if (currentDistance < parentDistance) {
this._swap(array, index, parentIndex);
}
bubbleUp(parentIndex, array);
};
bubbleUp(this.values.length - 1, this.values);
return this;
}
extractMin() {
this._swap(this.values, 0, this.values.length - 1);
let temp = this.values.pop();
const bubbleDown = (index, arr) => {
let { distance: parentDistance } = array[index];
let leftIndex = 2 * index + 1;
if (leftIndex >= array.length) return; // Check if left child index is out of bounds
let { distance: leftDistance } = array[leftIndex];
let rightIndex = 2 * index + 2;
let rightDistance;
if (rightIndex < array.length) {
rightDistance = array[rightIndex].distance;
}
if (parentDistance > leftDistance || parentDistance > rightDistance) {
if (!rightDistance || leftDistance <= rightDistance) {
this._swap(array, leftIndex, index);
bubbleDown(leftIndex, array);
} else {
this._swap(array, rightIndex, index);
bubbleDown(rightIndex, array);
}
}
};
bubbleDown(0, this.values);
return temp;
}
_swap(arr, index1, index2) {
let temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
export default MinHeap;For the extractMin() operation, the primary concept is to swap the value at the final index with the value at the first index of the array. We then set a pointer to the last index value and use the array pop() method to return it later when we finish the bubbleDown() method.
However, a challenge arises when we swap the final index value with the first index value, breaking the heap invariant. Since this is intentional and the last index value is now removed, our concern narrows down to the root. To address this, the bubbleDown() method comes to our aid, preventing a violation of the invariant.
The bubbleDown() operation mirrors bubbleUp() with some distinct constant factors. When relocating the root value to its correct position, and to maintain the heap invariant, we only compare it to the smaller child among its two children. If the left child is smaller than the right one, we compare the parent value with the left child. If the parent value is larger than the left child, we move it down recursively until it reaches its correct position. The same process applies to the right child.
When executing the bubbleDown() method, we commence at the root since the root value is now incorrectly placed, as discussed earlier.
The running time of the extractMin() method is the same as insert(), O(log2n).
At times, there might be a need to only find the min/max value of the heap without extracting it. In such cases, the method can be called findMin()/findMax(), and it’s much easier to implement than extractMin()/extractMax().
class MinHeap {
constructor() {
this.values = [];
}
insert(value) {
this.values.push(value);
const bubbleUp = (index, arr) => {
if (index <= 0) return;
let { distance: currentDistance } = array[index];
let parentIndex =
index % 2 === 0 ? (index - 2) / 2 : Math.floor((index - 1) / 2);
let { distance: parentDistance } = array[parentIndex];
if (currentDistance < parentDistance) {
this._swap(array, index, parentIndex);
}
bubbleUp(parentIndex, array);
};
bubbleUp(this.values.length - 1, this.values);
return this;
}
extractMin() {
this._swap(this.values, 0, this.values.length - 1);
let temp = this.values.pop();
const bubbleDown = (index, arr) => {
let { distance: parentDistance } = array[index];
let leftIndex = 2 * index + 1;
if (leftIndex >= array.length) return; // Check if left child index is out of bounds
let { distance: leftDistance } = array[leftIndex];
let rightIndex = 2 * index + 2;
let rightDistance;
if (rightIndex < array.length) {
rightDistance = array[rightIndex].distance;
}
if (parentDistance > leftDistance || parentDistance > rightDistance) {
if (!rightDistance || leftDistance <= rightDistance) {
this._swap(array, leftIndex, index);
bubbleDown(leftIndex, array);
} else {
this._swap(array, rightIndex, index);
bubbleDown(rightIndex, array);
}
}
};
bubbleDown(0, this.values);
return temp;
}
findMin() {
let temp = this.values[0];
return temp;
}
_swap(arr, index1, index2) {
let temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
export default MinHeap;As evident, we merely establish a pointer to the min/max value and promptly return it without extracting the min/max value from the heap. The runtime for this operation is amazingly O(1), denoting constant time.
And that should conclude our heap data structure implementation in JavaScript. Let’s continue to apply our new heap knowledge with this.