MinHeap implementation in JavaScript¶
Example:
class MinHeap {
constructor() {
this.heap = [];
}
_getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
_getLeftChildIndex(i) {
return 2 * i + 1;
}
_getRightChildIndex(i) {
return 2 * i + 2;
}
_getParent(i) {
return this.heap[this._getParentIndex(i)];
}
_getLeftChild(i) {
return this.heap[this._getLeftChildIndex(i)];
}
_getRightChild(i) {
return this.heap[this._getRightChildIndex(i)];
}
_hasParent(i) {
return this._getParentIndex(i) >= 0;
}
_hasLeftChild(i) {
return this._getLeftChildIndex(i) < this.heap.length;
}
_hasRightChild(i) {
return this._getRightChildIndex(i) < this.heap.length;
}
_swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
_heapifyUp() {
let i = this.heap.length - 1;
while (this._hasParent(i) && this._getParent(i) > this.heap[i]) {
let pi = this._getParentIndex(i);
this._swap(i, pi);
i = pi;
}
}
_heapifyDown() {
let i = 0;
while (this._hasLeftChild(i)) {
let smallerIndex = this._getLeftChildIndex(i);
if (this._hasRightChild(i) && this._getRightChild(i) < this._getLeftChild(i)) {
smallerIndex = this._getRightChildIndex(i);
}
if (this.heap[i] <= this.heap[smallerIndex]) {
break;
}
this._swap(i, smallerIndex);
i = smallerIndex;
}
}
push(item) {
this.heap.push(item);
this._heapifyUp();
}
isEmpty() {
return this.heap.length === 0;
}
pop() {
if (this.isEmpty()) {
return null;
}
if (this.heap.length === 1) {
return this.heap.pop();
}
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this._heapifyDown();
return min;
}
peek() {
return this.heap[0];
}
}