우선순위 큐 (Priority Queue)

Priority Queue

우선순위 큐(Priority Queue)는 요소들이 우선순위를 가지고 있으며, 높은 우선순위를 가진 요소들이 먼저 나올 수 있는 자료구조를 말합니다. 이전 포스트에 소개했던 힙을 그대로 사용하기 때문에, 사실 큐라고 하는 게 맞나 싶긴 하지만, 동작 자체가 큐와 동일하기 때문에 이런 명칭이 붙은 것 같기도 합니다. 힙과의 차이점은 노드에 우선순위를 할당 할 멤버 변수가 추가되었다는 것과 메소드의 이름이 큐에 맞게 변경된 것 말고는 없습니다. 그래도 힙이 선행되는 자료구조이기 때문에 꼭 이해해야 합니다.

그리고 우선순위 큐는 그래프 알고리즘 중 최소 신장 트리를 구성하는 프림 알고리즘과 최단 경로를 찾는 다익스트라 알고리즘 등에 활용할 수 있는 정말 유용한 자료구조입니다.

노드 & 클래스 생성

function Node({ priority, data }) {
  this.priority = priority;
  this.data = data;
}

function PriorityQueue() {
  Array.call(this);
}
PriorityQueue.prototype = Object.create(Array.prototype);
PriorityQueue.prototype.constructor = PriorityQueue;

앞서 언급한 것처럼 힙과 달라진 점으로, 노드에 우선순위를 의미하는 멤버 변수 priority가 추가되었습니다. 그리고 Array 프로토타입을 상속 받은 이유는 PriorityQueue로 만든 객체를 배열처럼 사용하기 위함입니다.

노드 추가 (Enqueue)

PriorityQueue.prototype.enqueue = function (newData) {
  let currentIndex = this.length;
  let parentIndex = this.getParent(currentIndex);

  this.push(newData);

  while (currentIndex > 0 && this[currentIndex].priority > this[parentIndex].priority) {
    this.swap(currentIndex, parentIndex);
    currentIndex = parentIndex;
    parentIndex = this.getParent(currentIndex);
  }
};

힙에서는 insert였던 이름이 큐에 맞춰 enqueue로 변경되었습니다. 내부 로직은 기존에는 값의 대소를 비교했다면, 우선순위 큐에서는 우선순위를 비교하여 큐를 구성합니다. 새로운 요소는 가장 마지막 위치에 삽입되므로, 부모 요소와 우선순위를 비교하여 위치를 바로 잡는 작업을 반복적으로 수행해야 합니다. 본문 예제에서는 큰 값의 priority를 가진 노드가 우선순위가 높은 것으로 가정했습니다.

루트 제거 (Dequeue)

PriorityQueue.prototype.dequeue = function () {
  const deleteNode = this[0];

  if (this.length === 1) {
    this.pop();
    return deleteNode;
  } else {
    this[0] = this.pop();
  }

  // Reconstruct PQ
  let parentIndex = 0;
  let leftChildIndex = this.getLeftChild(parentIndex);
  let rightChildIndex = leftChildIndex + 1;

  while (true) {
    let selectedIndex;

    if (leftChildIndex >= this.length) break;
    if (rightChildIndex >= this.length) {
      selectedIndex = leftChildIndex;
      if (this[selectedIndex].priority > this[parentIndex].priority) {
        this.swap(selectedIndex, parentIndex);
        parentIndex = selectedIndex;
      } else {
        break;
      }
    } else {
      if (this[leftChildIndex].priority > this[rightChildIndex].priority) selectedIndex = leftChildIndex;
      else selectedIndex = rightChildIndex;

      if (this[selectedIndex].priority > this[parentIndex].priority) {
        this.swap(selectedIndex, parentIndex);
        parentIndex = selectedIndex;
      } else {
        break;
      }
    }
    leftChildIndex = this.getLeftChild(parentIndex);
    rightChildIndex = leftChildIndex + 1;
  }

  return deleteNode;
};

우선순위가 가장 높은 요소가 루트에 위치하므로, 이를 제거하고 새로운 루트와 함께 큐를 재구성 해야 합니다. 맨 마지막 노드를 루트로 가져온 후 양쪽의 자식 노드들과 우선순위를 비교하며, 우선순위가 더 높은 노드가 위로 올라오도록 합니다. 노드 삽입 로직에 비해 상대적으로 코드의 길이가 길긴 하지만, 구현이 크게 달라지는 부분은 없어 간단한 편입니다.

유틸 메소드

PriorityQueue.prototype.swap = function (index1, index2) {
  [this[index1], this[index2]] = [this[index2], this[index1]];
};

PriorityQueue.prototype.getParent = function (index) {
  return Math.floor((index - 1) / 2);
};

PriorityQueue.prototype.getLeftChild = function (index) {
  return index * 2 + 1;
};

유틸 메소드는 반복적으로 호출되는 코드를 재사용 할 수 있도록 만든 것입니다.

References 📝

본문의 내용은 GeeksforGeeks의 Priority Queue 자료를 참고해 작성했습니다 ❤️