ZeroCho Blog

오랜만에 자료구조 포스팅으로 돌아왔습니다. 이번 시간에는 우선순위 큐를 구현해보도록 하겠습니다.

우선순위 큐는 큐 에서 진화된 형태로, 맨 뒤에만 추가되고 맨 앞에서만 나가는 기본적인 FIFO 큐와는 다르게, 우선순위가 높은 노드가 먼저 나갈 수 있습니다. 따라서 일반적인 대기열이 아니라 중요도가 나눠져 있는 대기열을 구현할 때 좋습니다. 줄 서는 시스템에서 VIP를 우대한다든가(자본주의 세상!!!)... 태스크들이 있을 때 긴급 태스크를 먼저 처리하게 한다든가...

우선순위 큐는 힙 (이진 힙)을 사용해서 구현할 수 있습니다. 힙에다 새로운 값을 넣는 게 우선순위 큐에 값을 넣는 것이고, 힙에서 값을 빼는게 우선순위 큐에 값을 제거하는 것입니다. 힙 소스코드에 데이터를 추가로 받게끔 수정하면 됩니다.

class PriorityQueue {
  arr = [];

  #reheapUp(self, idx) {
    if (idx) {
      const parent = parseInt((idx - 1) / 2);
      if (self.arr[idx].priority > self.arr[parent].priority) {
        const temp = self.arr[idx];
        self.arr[idx] = self.arr[parent];
        self.arr[parent] = temp;
        this.#reheapUp(self, parent);
      }
    }
  }

  #reheapDown(self, idx) {
    let left = 0;
    let right = 0;
    let large;
    if (idx * 2 + 1 < self.arr.length) {
      left = self.arr[idx * 2 + 1].priority;
      if (idx * 2 + 2 < self.arr.length - 1) {
        right = self.arr[idx * 2 + 2].priority;
      }
      if (left > right) {
        large = idx * 2 + 1;
      } else {
        large = idx * 2 + 2;
      }
      if (self.arr[idx].priority < self.arr[large].priority) {
        const temp = self.arr[idx];
        self.arr[idx] = self.arr[large];
        self.arr[large] = temp;
        this.#reheapDown(self, large);
      }
    }
  }
 
  insert(priority, data) {
    const last = this.arr.length;
    this.arr[last] = {}; // 객체로 변경
    this.arr[last].priority = priority;
    this.arr[last].data = data;
    this.#reheapUp(this, last);
    return true;
  };
 
  delete() {
    if (this.arr.length === 0) {
      return false;
    }
    const del = this.arr[0];
    this.arr[0] = this.arr.pop();
    this.#reheapDown(this, 0);
    return del.data;
  };
 
  peek() {
    return this.arr[0]?.data;
  };
}

insert 시 priority와 data를 받도록 수정했습니다. #reheapUp, #reheapDown에서도 priority를 기반으로 데이터를 교체합니다.

const pq = new PriorityQueue();
pq.insert(5, 'one');
pq.insert(3, 'two');
pq.insert(4, 'three');
pq.insert(2, 'four');
pq.insert(6, 'five');
pq.insert(1, 'six');
pq.insert(7, 'king'); // 새치기
pq.delete(); // 'king'
pq.peek(); // 'five'

FIFO 큐와 비교할 때 큐를 넣는 것, 빼는 것이 모두 O(lg(n))으로 시간 복잡도가 증가했지만 이 정도면 충분히 실전에서 사용할 수 있습니다.

우선순위 큐는 다른 자료구조로도 구현할 수는 있습니다. 정렬된 배열이나, 피보나치 힙, 이항 힙 등으로도 구현 가능합니다. 하지만 성능이 이진 힙보다 낮거나, 좋더라도 구현이 복잡하기에 이진 힙으로 만족하는 편입니다.