Super Basic -> Min and Max Priority Queue

gistfile1.txt

class Node {
  constructor(val, priority = val) {
    this.val = val;
    this.priority = priority;
  }
}

// Min
class MinPriorityQueue {
  constructor() {
    this.heap = [];
  }

  isEmpty() {
    return !this.heap.length;
  }
  
  size(){
    return this.heap.length
  }

  peek() {
    return this.heap[0];
  }

  enqueue(val, priority) {
    const node = new Node(val, priority);
    this.heap.push(node);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      let parentIdx = Math.floor((index - 1) / 2);
      let parentElement = this.heap[parentIdx];
      let currentElement = this.heap[index];

      if (parentElement.priority <= currentElement.priority) break;

      this.heap[parentIdx] = currentElement;
      this.heap[index] = parentElement;

      index = parentIdx;
    }
  }

  dequeue() {
    const min = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return min;
  }

  heapifyDown(i = 0) {
    let smallest = i;
    let left = 2 * i + 1;
    let right = left + 1;
    const length = this.heap.length;

    if (
      left < length &&
      this.heap[left].priority < this.heap[smallest].priority
    )
      smallest = left;
    if (
      right < length &&
      this.heap[right].priority < this.heap[smallest].priority
    )
      smallest = right;

    if (smallest != i) {
      const temp = this.heap[smallest];
      this.heap[smallest] = this.heap[i];
      this.heap[i] = temp;

      this.heapifyDown(smallest);
    }
  }
}


// MAX Priority Queue
class Node {
  constructor(val, priority = val) {
    this.val = val;
    this.priority = priority;
  }
}

class MaxPriorityQueue {
  constructor() {
    this.heap = [];
  }

  isEmpty() {
    return !this.heap.length;
  }
  
  size(){
    return this.heap.length
  }

  enqueue(val, priority) {
    const node = new Node(val, priority);
    this.heap.push(node);
    this.heapifyUp();
  }

  heapifyUp() {
    let i = this.heap.length - 1;

    while (i > 0) {
      const parentIdx = Math.floor((i - 1) / 2);
      const parentElement = this.heap[parentIdx];
      const currentElement = this.heap[i];

      if (parentElement.priority >= currentElement.priority) break;

      this.heap[parentIdx] = currentElement;
      this.heap[i] = parentElement;
      i = parentIdx;
    }
  }

  dequeue() {
    const max = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown(0);
    return max;
  }

  heapifyDown(i = 0) {
    let largest = i;
    let leftChildIdx = 2 * i + 1;
    let rightChildIx = 2 * i + 2;
    let length = this.heap.length;

    if (
      leftChildIdx < length &&
      this.heap[leftChildIdx].priority > this.heap[largest].priority
    )
      largest = leftChildIdx;
    if (
      rightChildIx < length &&
      this.heap[rightChildIx].priority > this.heap[largest].priority
    )
      largest = rightChildIx;

    if (largest !== i) {
      [this.heap[largest], this.heap[i]] = [this.heap[i], this.heap[largest]];
      this.heapifyDown(largest);
    }
  }
}