Heap

Max Heap (Javascript)

class MaxHeap {
  constructor(capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.arr = [];
  }

  add(val) {
    if (this.size < this.capacity) {
      this.arr[this.size++] = val;
      this.trickleUp(this.size - 1);
    }
  }

  trickleUp(i) {
    const parent = Math.floor((i - 1) / 2);
    if (parent >= 0 && this.arr[i] > this.arr[parent]) {
      this.swap(i, parent);
      this.trickleUp(parent);
    }
  }

  delete() {
    if (this.size) {
      const ret = this.arr[0];
      this.arr[0] = this.arr[this.size-- - 1];
      this.trickleDown(0);
      return ret;
    }
  }

  trickleDown(i) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;
    if (left < this.size && this.arr[left] > this.arr[largest]) {
      largest = left;
    }
    if (right < this.size && this.arr[right] > this.arr[largest]) {
      largest = right;
    }
    if (largest !== i) {
      this.swap(i, largest);
      this.trickleDown(largest);
    }
  }

  swap(a, b) {
    const temp = this.arr[a];
    this.arr[a] = this.arr[b];
    this.arr[b] = temp;
  }

  hasNext() {
    return this.size > 0;
  }
}

/** Test **/
const maxHeap = new MaxHeap(1000);
maxHeap.add(1);
maxHeap.add(90);
maxHeap.add(11);
maxHeap.add(5);
while (maxHeap.hasNext()) {
  console.log(maxHeap.delete());
}

/* 
 Output:
     		90
     		11
     		5
     		1
*/

// Time complexity for each operation: O(log(n)).

Demo