Priority Queue/Binary Heap Implementation in JS

I. Why?

Because in JS, there is NO such useful build-in data structure🤣…….

[Great Links]: https://www.cs.usfca.edu/~galles/visualization/Heap.html

II. Time Complexity

1. construct: O(n)
2. peek: O(1)
3. offer: O(lgn)
4. poll: O(lgn)

III. Implementation

/**
 * Priority Queue
 *
 * Binary Heap implementation
 *
 * clear: Removes all of the elements from this priority queue.
 * offer: Inserts the specified element into this priority queue.
 * peek: Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
 * poll: Retrieves and removes the head of this queue, or returns null if this queue is empty.
 * size: Returns the number of elements in this collection.
 * toArray: Returns an array containing all of the elements in this queue.
 */

class BinomialHeap {
  constructor({
    comparator = (a, b) => a - b, 
    initialValues = [] 
  } = {}) {
    this.comparator = comparator;
    this.data = initialValues;
    this.heapify();
  }

  
  heapify() {
    if (this.isEmpty()) {
      return;
    }
    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i);
    }
  }

  offer(newNode) {
    this.data.push(newNode);
    this.bubbleUp(this.size() - 1);
  }

  poll() {
    if (this.isEmpty()) {
      return null;
    }

    let res = this.data[0];
    let last = this.data.pop();

    if (this.size() > 0) {
      this.data[0] = last;
      this.sinkDown(0);
    }
    return res;
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.data[0];
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.data.length;
  }

  toArray() {
    return this.data.slice();
  }

  clear() {
    this.data = [];
  }

  bubbleUp(pos) {
    while (pos > 0) {
      let parentIndex = (pos - 1) >>> 1;
      if (this.comparator(this.data[parentIndex], this.data[pos]) > 0) {
        [this.data[parentIndex], this.data[pos]] = [this.data[pos], this.data[parentIndex]];
        pos = parentIndex;
      } else {
        break;
      }
    }
  }

  sinkDown(pos) {
    let size = this.size();
    while (true) {
      let left = (pos << 1) + 1;
      let right = left + 1;
      let minIndex = pos;

      if (left < size && this.comparator(this.data[left], this.data[minIndex]) < 0) {
        minIndex = left;
      }

      if (right < size && this.comparator(this.data[right], this.data[minIndex]) < 0) {
        minIndex = right;
      }

      if (minIndex !== pos) {
        [this.data[minIndex], this.data[pos]] = [this.data[pos], this.data[minIndex]];
        pos = minIndex;
      } else {
        break;
      }
    }
  }
}



// TEST cases:
class Node{
  constructor(k, v) {
    this.k = k;
    this.v = v;
  }
}

let pq = new BinomialHeap({
  comparator: (n1, n2) => n1.v - n2.v,
  initialValues: [
    new Node('c', 3), 
    new Node('f', 6), 
    new Node('b', 2), 
    new Node('d', 4), 
    new Node('a', 1), 
    new Node('e', 5),
    new Node('g', 7),
  ]
});

console.log("toArray(): should be [1, 2, 3, 6, 4, 5, 7]    ", pq.toArray());
console.log("smallest should be: Node {k: 'a', v: 1}   ", pq.peek());
console.log("size should be 7   ", pq.size());

let smallest = pq.poll();
console.log("smallest should be: Node {k: 'a', v: 1}   ", smallest);
console.log("size should be 6   ", pq.size());
console.log("toArray(): should be [2, 4, 3, 6, 7, 5]    ", pq.toArray());

pq.offer(new Node('aa', 1));
console.log("toArray(): should be [1, 4, 2, 6, 7, 5, 3]    ", pq.toArray());
console.log("size should be 7   ", pq.size());