heap.js

heap.js

class Heap {
  constructor(sorter) {
    this.sorter = sorter;
    this.arr = [];
  }
  get length() {
    return this.arr.length;
  }

  push(el) {
    this.arr.push(el);
    let current = this.arr.length - 1;
    let parent = Math.max(0, Math.floor((current - 1) / 2));
    while (this.sorter(this.arr[current], this.arr[parent]) > 0) {
      [this.arr[current], this.arr[parent]] = [this.arr[parent], this.arr[current]];
      current = parent;
      parent = Math.max(0, Math.floor((current - 1) / 2));
    }
  }

  get peak() {
    return this.arr[0];
  }

  pop() {
    if (this.arr.length === 0) {
      return null;
    }
    const peak = this.arr[0];
    this.arr[0] = this.arr[this.arr.length - 1];
    this.arr.pop();
    let current = 0;
    let left = 1;
    let rigth = 2;
    while(left < this.arr.length) {
      if (this.sorter(this.arr[current], this.arr[left]) < 0) {
          if (rigth < this.arr.length && (this.sorter(this.arr[left], this.arr[rigth]) < 0)) {
            [this.arr[current], this.arr[rigth]] = [this.arr[rigth], this.arr[current]];
            current = rigth;
          } else {
             [this.arr[current], this.arr[left]] = [this.arr[left], this.arr[current]];
             current = left;
          }
      } else if ((rigth < this.arr.length) && (this.sorter(this.arr[current], this.arr[rigth]) < 0)) {
        [this.arr[current], this.arr[rigth]] = [this.arr[rigth], this.arr[current]];
        current = rigth;
      } else {
        break;
      }
      left = current * 2 + 1;
      rigth = current * 2 + 2;
    }
    return peak;
  }
}