Skip to content

Instantly share code, notes, and snippets.

@SobolevskyDmitry
Last active February 17, 2022 13:36
Show Gist options
  • Save SobolevskyDmitry/7a6c1a45fd79b6b2a08519f454b14f72 to your computer and use it in GitHub Desktop.
Save SobolevskyDmitry/7a6c1a45fd79b6b2a08519f454b14f72 to your computer and use it in GitHub Desktop.
Heap with comparator function (Min Heap, Max Heap)
class Heap {
constructor(arr, comparator) {
this.values = [];
this.comparator = comparator;
if (arr) {
this.build(arr);
}
}
leftIndex(i) {
return i * 2 + 1;
}
rightIndex(i) {
return i * 2 + 2;
}
parent(i) {
return Math.floor(i / 2);
}
build(arr) {
arr.forEach(val => this.add(val));
}
heapify(i) {
let largest = i, leftChild = this.leftIndex(i), rightChild = this.rightIndex(i);
if (this.values[leftChild] && this.comparator(this.values[largest], this.values[leftChild])) {
largest = leftChild;
}
if(this.values[rightChild] && this.comparator(this.values[largest], this.values[rightChild])) {
largest = rightChild
};
if (largest !== i) {
this.swap(i, largest);
this.heapify(largest);
}
}
add(val) {
this.values.push(val);
for(let i = Math.floor(this.size() / 2 -1); i >= 0; i--){
this.heapify(i)
}
}
size() {
return this.values.length;
}
swap(i,j) {
[this.values[i], this.values[j]] = [this.values[j], this.values[i]];
}
peek() {
return this.values[0];
}
pull() {
const max = this.values.shift();
this.heapify(0);
return max;
}
}
// example:
const heap = new Heap([3,9,1,2,4,5], (a,b) => a < b);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment