Skip to content

Instantly share code, notes, and snippets.

@mwdchang

mwdchang/heap.js

Created March 4, 2021 04:42
Show Gist options
  • Save mwdchang/6851cc8657d96da71b42940ba96d7bdc to your computer and use it in GitHub Desktop.
Save mwdchang/6851cc8657d96da71b42940ba96d7bdc to your computer and use it in GitHub Desktop.
Download ZIP
Simple quickie binary heap
Raw
heap.js
class Heap {
constructor(maxsize) {
this.size = 0;
this.maxsize = maxsize;
this.data = [this.maxsize + 1];
}
getParent(index) { return Math.round( index / 2); }
getLeftChild(index) { return 2 * index; }
getRightChild(index) { return 2 * index + 1; }
isLeaf(index) { return index >= this.size / 2 && index <= this.size; }
swap(indexA, indexB) {
const tmp = this.data[indexA];
this.data[indexA] = this.data[indexB];
this.data[indexB] = tmp;
}
heapify(index) {
if (this.isLeaf(index)) return;
const data = this.data;
const v = data[index];
const leftChildIndex = this.getLeftChild(index);
const rightChildIndex = this.getRightChild(index);
if (v > data[leftChildIndex] || v > data[rightChildIndex]) {
if (data[leftChildIndex] < data[rightChildIndex]) {
this.swap(index, leftChildIndex);
this.heapify(this.getLeftChild(index));
} else {
this.swap(index, rightChildIndex);
this.heapify(this.getRightChild(index));
}
}
}
insert(v) {
if (this.size >= this.maxsize) return;
this.data[++this.size] = v;
let currentIndex = this.size;
while (this.data[currentIndex] < this.data[this.getParent(currentIndex)]) {
this.swap(currentIndex, this.getParent(currentIndex));
currentIndex = this.getParent(currentIndex);
}
}
remove() {
const v = this.data[1];
this.data[1] = this.data[this.size - 1];
this.size --;
this.heapify(1);
return v;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment