Implementing a Complete Binary Heap in JavaScript: The Priority Queue

code.js

// https://codeburst.io/implementing-a-complete-binary-heap-in-javascript-the-priority-queue-7d85bd256ecf

// Linked list
class Node {
  constructor(val, priority) {
    this.val = val;
    this.priority = priority;
    this.next = null;
  }
}

class PriorityQueue {
  constructor() {
    this.first = null;
  }
  insert(value, priority) {
    const newNode = new Node(value, priority);
    if (!this.first || priority > this.first.priority) {
      // When the new node has higher priority, the first node should be after the new node.
      newNode.next = this.first;
      this.first = newNode;
    } else {
      let pointer = this.first;
      // O(N)
      while (pointer.next && priority < pointer.next.priority) {
        // Look up higher (or same) node.
        pointer = pointer.next;
      }
      // Inserting after the pointer
      newNode.next = pointer.next;
      pointer.next = newNode;
    }
  }
  remove() {
    const first = this.first;
    this.first = this.first.next;
    return first;
  }
}

// Binary Heap
// 1. The priority of the node that gets inserted cannot be greater than its parent.
// 2. Every level of the heap must be full, except the lowest level, which fills left to right.
class BinaryHeapQueue {
  constructor() {
    this.heap = [null];
  }
  insert(value, priority) {
    const newNode = new Node(value, priority);
    // Add new node into the array.
    this.heap.push(newNode);
    // Initialize nodeIdx
    let currentNodeIdx = this.heap.length - 1;
    let currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
    while (this.heap[currentNodeParentIdx] &&
      newNode.priority > this.heap[currentNodeParentIdx].priority) {
      // While the parent exists, and the parent is smaller than the new node
      const parentNode = this.heap[currentNodeParentIdx];
      // Set new higher node as parent
      this.heap[currentNodeParentIdx] = newNode;
      // Parent becomes new node's child
      this.heap[currentNodeIdx] = parentNode;
      // Refresh indexes
      currentNodeIdx = currentNodeParentIdx;
      currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
    }
  }
  remove() {
    if (this.heap.length < 3) {
      const toReturn = this.heap.pop();
      this.heap[0] = null;
      return toReturn;
    }
    const toRemove = this.heap[1];
    this.heap[1] = this.heap.pop(); // The last one comes to top
    let currentIdx = 1;
    // Get children's index
    let [left, right] = [2 * currentIdx, 2 * currentIdx + 1];
    // Pick the child's index
    let currentChildIdx = this.heap[right].priority >= this.heap[left].priority ? right : left;
    while (this.heap[currentChildIdx] &&
      this.heap[currentIdx].priority <= this.heap[currentChildIdx].priority) {
      // While the child exists, and the child is higher than the parent
      // Swap the child and parent(current)
      let currentNode = this.heap[currentIdx];
      let currentChildNode = this.heap[currentChildIdx];
      this.heap[currentIdx] = currentChildNode;
      this.heap[currentChildIdx] = currentNode;
    }
    return toRemove;
  }
}

const queue = new BinaryHeapQueue();
[100, 19, 36, 17, 3, 25, 1, 2, 7].map((mem, idx) => {
  return queue.insert(mem, idx);
});
console.log(queue.heap.filter((m) => m).sort((a, b) => a.priority === b.priority ? 0 : a.priority > b.priority ? 1 : -1).map((m) => `${m.val}, ${m.priority}`));
queue.remove();
console.log(queue.heap.filter((m) => m).sort((a, b) => a.priority === b.priority ? 0 : a.priority > b.priority ? 1 : -1).map((m) => `${m.val}, ${m.priority}`));