Skip to content

Instantly share code, notes, and snippets.

@johnnyeric
Last active June 21, 2020 15:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save johnnyeric/d1ad07e6927213a993effd888590922b to your computer and use it in GitHub Desktop.
Save johnnyeric/d1ad07e6927213a993effd888590922b to your computer and use it in GitHub Desktop.
Min Heap JavaScript implementation
// Based on AlgoExpert's version
class MinHeap {
heap = null;
constructor(array) {
this.heap = array;
this.buildHeap();
}
buildHeap() {
const firstParentIndex = Math.floor((this.heap.length - 2) / 2);
for (let currentIndex = firstParentIndex; currentIndex >= 0; currentIndex--) {
this.siftDown(currentIndex, this.heap.length);
}
}
siftDown(currentIndex, endIndex) {
let childOneIndex = currentIndex * 2 + 1;
while (childOneIndex <= endIndex) {
let childTwoIndex = -1;
if (currentIndex * 2 + 2 <= endIndex) {
childTwoIndex = currentIndex * 2 + 2;
}
let indexToSwap = childOneIndex;
if (childTwoIndex > -1 && this.heap[childTwoIndex] < this.heap[childOneIndex]) {
indexToSwap = childTwoIndex;
}
if (this.heap[indexToSwap] < this.heap[currentIndex]) {
this.swap(currentIndex, indexToSwap);
currentIndex = indexToSwap;
childOneIndex = currentIndex * 2 + 1;
} else {
return;
}
}
}
siftUp() {
let currentIndex = this.heap.length - 1;
let parentIndex = Math.floor((currentIndex - 1) / 2);
while (currentIndex >= 0 && this.heap[currentIndex] < this.heap[parentIndex]) {
this.swap(currentIndex, parentIndex);
currentIndex = parentIndex;
parentIndex = Math.floor((currentIndex - 1) / 2);
}
}
remove() {
this.swap(0, this.heap.length - 1);
const peek = this.heap.pop();
this.siftDown(0, this.heap.length - 1);
return peek;
}
peek() {
if (this.heap.length == 0) {
return -1;
}
return this.heap[0];
}
insert(value) {
this.heap.push(value);
this.siftUp();
}
swap(i,j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
}
isEmpty() {
return this.heap.length === 0;
}
}
const heap = new MinHeap([]);
heap.insert(9);
heap.insert(4);
heap.insert(20);
heap.insert(2);
heap.insert(3);
console.log(heap.peek());
heap.insert(1);
console.log(heap.peek());
console.log(heap.remove());
console.log(heap.peek());
console.log(heap.isEmpty());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment