JavaScript에서 우선순위 큐(Priority Queue) 구현하기

Intro

나는 자바로 알고리즘에 입문했다.

타입 안정성이나 후술할 우선순위 큐(Priority Queue)와 같은 다양한 내장 클래스 역시 Java가 더 편하다고 느끼지만, 프론트엔드 직무의 코딩 테스트에서 자바스크립트로 언어를 강제하는 경우가 많고, 나 역시 자바스크립트가 이제는 더 익숙해졌기 때문에 이제는 자바스크립트로 문제를 풀고 있다.

알고리즘 문제의 난이도가 올라갈 수록, 이를테면 다익스트라와 같은 경로 탐색 알고리즘이라던지, 우선순위 큐가 활용되는 경우가 많은데, 자바스크립트의 경우 별도로 구현되지 않아서 직접 구현해서 사용해야한다.

물론 우선순위 큐가 없어도 최단 경로를 구할 수 있지만, 그렇게 구하는 건 시간 복잡도 측면에서 이점이 없으며 문제를 통과하지 못할 확률이 아주 높다.

1. 우선순위 큐(Priority Queue)

우선순위 큐란?

Queue라고 함은 선입선출(FIFO, First In First Out) 의 규칙을 따른다.

그러나 우선순위 큐(Priority Queue)는 우선순위에 따라 요소를 삽입하고 삭제하는 자료구조다.

선입선출의 규칙 대신, 우선순위가 높은 요소가 먼저 나가는 규칙을 따른다.

예제

우선순위 큐의 동작 방식을 간단한 예로 살펴보자.

우리가 작업 목록을 관리한다고 가정하자. 각각의 작업은 이름과 우선순위를 가진다.
Task 1 (우선순위 3), Task 2 (우선순위 1), Task 3 (우선순위 2)를 삽입한다고 해보자.
우선순위 큐에서 가장 먼저 나갈 작업은 Task 2(우선순위 1)이다.

2. JavaScript로 힙(Heap) 구현하기

우선순위 큐를 효율적으로 구현하려면 힙(Heap) 자료구조가 필요하다.

힙은 트리 기반 자료구조로, 최소값(최소 힙) 또는 최대값(최대 힙)을 빠르게 추출할 수 있다.

최소 힙 (MinHeap) 구현

아래는 JavaScript로 최소 힙을 구현한 코드다.

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

  // 부모 노드의 인덱스 계산
  getParent(index) {
    return Math.floor((index - 1) / 2);
  }

  // 왼쪽 자식 노드의 인덱스 계산
  getLeftChild(index) {
    return index * 2 + 1;
  }

  // 오른쪽 자식 노드의 인덱스 계산
  getRightChild(index) {
    return index * 2 + 2;
  }

  push(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  pop() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return root;
  }

  // 힙의 최상위 값
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  // 힙을 위로 재정렬
  heapifyUp() {
    let index = this.heap.length - 1;

    while (index > 0 && this.heap[index] < this.heap[this.getParent(index)]) {
      const parent = this.getParent(index);
      [this.heap[index], this.heap[parent]] = [
        this.heap[parent],
        this.heap[index],
      ];
      index = parent;
    }
  }

  // 힙을 아래로 재정렬
  heapifyDown() {
    let index = 0;

    while (this.getLeftChild(index) < this.heap.length) {
      let smallerChild = this.getLeftChild(index);
      const rightChild = this.getRightChild(index);

      if (
        rightChild < this.heap.length &&
        this.heap[rightChild] < this.heap[smallerChild]
      ) {
        smallerChild = rightChild;
      }

      if (this.heap[index] <= this.heap[smallerChild]) {
        break;
      }

      [this.heap[index], this.heap[smallerChild]] = [
        this.heap[smallerChild],
        this.heap[index],
      ];

      index = smallerChild;
    }
  }
}

// 테스트
const heap = new MinHeap();
heap.push(10);
heap.push(5);
heap.push(20);
console.log(heap.pop()); // 5
console.log(heap.pop()); // 10
console.log(heap.pop()); // 20

3. JavaScript로 Priority Queue 구현하기

위에서 구현한 MinHeap을 활용해 우선순위 큐를 구현할 수 있다.

class PriorityQueue {
  constructor() {
    this.heap = new MinHeap();
  }

  enqueue(element, priority) {
    this.heap.push({ element, priority });
  }

  dequeue() {
    const min = this.heap.pop();
    return min ? min.element : null;
  }

  peek() {
    const min = this.heap.peek();
    return min ? min.element : null;
  }
}

// 테스트
const pq = new PriorityQueue();
pq.enqueue('Task 1', 3);
pq.enqueue('Task 2', 1);
pq.enqueue('Task 3', 2);

console.log(pq.dequeue()); // "Task 2"
console.log(pq.dequeue()); // "Task 3"
console.log(pq.dequeue()); // "Task 1"

4. 왜 JavaScript에 Priority Queue가 없을까?

언어의 설계 철학

JavaScript는 초기 웹 브라우저 스크립팅 언어로 설계되었으며, 간단하고 유연한 도구를 제공하는 데 초점을 맞췄다.

복잡한 자료구조 대신, 최소한의 기본 자료구조(Array, Object)를 제공하며, 필요한 기능은 커스터마이징할 수 있도록 설계되었다.

필요성의 부재

JavaScript는 주로 프론트엔드 개발에 사용되었기 때문에, 알고리즘 문제나 복잡한 자료구조가 필요한 경우가 드물었다.

백엔드 언어처럼 고급 자료구조가 기본 제공되지 않아도 큰 문제가 없었다.

라이브러리 생태계

JavaScript는 라이브러리와 패키지를 통해 부족한 기능을 쉽게 보완할 수 있다.

npm에는 heap.js, fastpriorityqueue와 같은 패키지가 이미 존재하며, 이를 활용하면 내장 자료구조가 없어도 문제를 해결할 수 있다.

마무리

JavaScript로 알고리즘 문제를 풀기 위해 우선순위 큐를 구현하는 방법을 배웠다.

JavaScript는 내장 Priority Queue를 제공하지 않지만, 힙을 직접 구현하거나, 라이브러리를 활용하여 간단히 문제를 해결할 수 있다.

코딩테스트를 수차례 경험한 결과, JavaScript만 사용하는 코딩테스트에서는 구현하는 문제가 거의 없지만, 다익스트라와 같이 우선순위 큐가 필요한 경우, 직접 구현하여 사용하는 것이 더 효율적이고 활용도가 높다고 생각한다.