MinMaxPriorityQueue

MinMaxPriorityQueue.js

class MinMaxPriorityQueue {

  #heap = []
  #compare;

  constructor(compare = (a, b) => a - b) {
    this.#compare = compare; // Default to Min-Heap if no compare function is provided
  }

  // Add a new element to the priority queue
  enqueue = (value) => {
    this.#heap.push(value);
    this.#heapifyUp(this.#heap.length - 1);
  }

  // Remove and return the element with the highest priority (smallest for min-heap, largest for max-heap)
  dequeue = () => {
    if (this.#heap.length === 0) return null;
    const root = this.#heap[0];
    const end = this.#heap.pop();
    if (this.#heap.length > 0) {
      this.#heap[0] = end;
      this.#heapifyDown(0);
    }
    return root;
  }

  // Peek at the element with the highest priority without removing it
  peek = () => {
    return this.#heap.length > 0 ? this.#heap[0] : null;
  }

  // Check if the priority queue is empty
  isEmpty = () => {
    return this.#heap.length === 0;
  }

  // Get the size of the priority queue
  size = () => {
    return this.#heap.length;
  }
  
  // Get the heap
  get heap() {
    return this.#heap
  }

  // Maintain heap property by moving element up
  #heapifyUp = (index) => {
    let parent = Math.floor((index - 1) / 2);
    while (index > 0 && this.#compare(this.#heap[index], this.#heap[parent]) < 0) {
      this.#swap(index, parent)
      index = parent;
      parent = Math.floor((index - 1) / 2);
    }
  }

  // Maintain heap property by moving element down
  #heapifyDown = (index) => {
    const length = this.#heap.length;
    let left = 2 * index + 1;
    let right = 2 * index + 2;
    let extreme = index;

    if (left < length && this.#compare(this.#heap[left], this.#heap[extreme]) < 0) {
      extreme = left;
    }

    if (right < length && this.#compare(this.#heap[right], this.#heap[extreme]) < 0) {
      extreme = right;
    }

    if (extreme !== index) {
      this.#swap(index, extreme)
      this.#heapifyDown(extreme);
    }
  }

  #swap = (i, j) => {
    [this.#heap[i], this.#heap[j]] = [this.#heap[j], this.#heap[i]]
  }
}