[JS] 우선순위 큐(Priority Queue) 구현하기

최소 힙(Min Heap)을 사용해 우선순위 큐(Priority Queue) 구현

class PriorityQueue {
  constructor() {
    this.minHeap = [];
  }

  enqueue(value, priority) {
    this.minHeap.push({ value, priority });
    this.heapUp();
  }

  dequeue() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.minHeap.pop();

    const min = this.minHeap[0];
    this.minHeap[0] = this.minHeap.pop();
    this.heapDown();

    return min;
  }

  heapUp() {
    let child = this.size() - 1;

    while (child > 0) {
      const parent = this.getParent(child);
      if (this.isHigherPriorityThan(parent, child)) break;

      this.swap(child, parent);
      child = parent;
    }
  }

  heapDown() {
    let parent = 0;

    while (true) {
      const left = this.getLeftChild(parent);
      const right = this.getRightChild(parent);
      let highest = parent;

      if (this.isValidChild(left) && this.isHigherPriorityThan(left, highest))
        highest = left;

      if (this.isValidChild(right) && this.isHigherPriorityThan(right, highest))
        highest = right;

      if (highest === parent) break;

      this.swap(parent, highest);
      parent = highest;
    }
  }

  isHigherPriorityThan(a, b) {
    if (this.minHeap[a].priority < this.minHeap[b].priority) return true;

    return false;
  }

  swap(a, b) {
    [this.minHeap[a], this.minHeap[b]] = [this.minHeap[b], this.minHeap[a]];
  }

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

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

  getParent(child) {
    return Math.floor((child - 1) / 2);
  }
  getLeftChild(parent) {
    return parent * 2 + 1;
  }
  getRightChild(parent) {
    return parent * 2 + 2;
  }
  isValidChild(index) {
    return index < this.size();
  }
}

 

value에는 저장할 값, priority에는 우선순위 비교를 위한 값이 들어갑니다.

isHigherPriorityThan(a, b)는 우선 순위 비교를 위한 메서드입니다. 더 복잡한 비교가 필요할 경우, 이 부분을 수정하면 됩니다.