Skip to content

Instantly share code, notes, and snippets.

@cwli24
Last active May 2, 2022 03:09
Show Gist options
  • Save cwli24/5cd2566dcd0ff04f6fbdaee968dc5ec5 to your computer and use it in GitHub Desktop.
Save cwli24/5cd2566dcd0ff04f6fbdaee968dc5ec5 to your computer and use it in GitHub Desktop.
Generic min heap class for JS (which lacks that DS built-in)
class MinHeap {
constructor(selector = x => x[0]) {
this.items = [0];
this.selector = selector;
}
insert(item) {
let childIdx = this.items.length;
this.items.push(item);
let childItem = item;
let parentIdx = Math.trunc(childIdx/2), parentItem = this.items[parentIdx];
while (childIdx > 1 && this.selector(parentItem) > this.selector(childItem)) {
[this.items[childIdx], this.items[parentIdx]] = [parentItem, childItem];
childIdx = parentIdx;
childItem = this.items[childIdx];
parentIdx = Math.trunc(childIdx/2);
parentItem = this.items[parentIdx];
}
}
remove() {
let initialLen = this.items.length - 1;
if (initialLen == 1)
return this.items.pop();
else if (initialLen <= 0)
return undefined;
const itemToReturn = this.items[1];
this.items[1] = this.items.pop();
let parentIdx = 1;
let leftChildIdx;
// Remember that heaps are complete trees--left is assigned before right
while ((leftChildIdx = parentIdx*2) < initialLen) {
let rightChildIdx = leftChildIdx + 1;
let smallerChildIdx;
if (rightChildIdx >= initialLen) {
smallerChildIdx = leftChildIdx;
} else {
smallerChildIdx = this.selector(this.items[leftChildIdx]) < this.selector(this.items[rightChildIdx]) ?
leftChildIdx : rightChildIdx;
}
let parentItem = this.items[parentIdx];
let smallerChildItem = this.items[smallerChildIdx];
if (this.selector(parentItem) > this.selector(smallerChildItem)) {
[this.items[smallerChildIdx], this.items[parentIdx]] = [parentItem, smallerChildItem];
parentIdx = smallerChildIdx;
} else {
break;
}
}
return itemToReturn;
}
isEmpty() {
return this.items.length <= 1;
}
size() {
return this.items.length-1;
}
peek() {
if (this.items.length <= 1)
return undefined;
return this.items[1];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment