[javascript] 우선순위 큐 (Priority Queue) 데이터 구조

08 Dec 2023

javascript

우선순위 큐는 데이터를 담는 일반적인 큐와 다르게 각 요소가 우선순위와 함께 저장되는 데이터 구조입니다. 이는 가장 높은 우선순위를 가진 요소가 먼저 처리되는 특징을 가지고 있습니다.

우선순위 큐의 작동 방식

우선순위 큐는 매우 다양한 방식으로 구현될 수 있습니다. 가장 간단한 형태는 정렬된 배열을 사용하여 구현하는 것이며, 이 경우 삽입 및 삭제 연산 시간이 O(n)으로 이루어집니다. 더 효율적인 구현 방법으로는 이진 힙(Binary Heap)을 사용하는 방법이 있으며, 최악의 경우에도 O(log n)의 시간복잡도로 삽입 및 삭제 연산을 수행할 수 있습니다.

JavaScript에서 우선순위 큐 구현하기

자바스크립트에서 우선순위 큐를 구현하기 위해서는 보통 배열 또는 힙을 활용합니다. 아래는 배열을 사용한 간단한 예시입니다.

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

  enqueue(element, priority) {
    let queueElement = { element, priority };
    let added = false;
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    if (!added) this.items.push(queueElement);
  }

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

위의 코드는 배열을 사용하여 우선순위 큐를 구현한 것으로, enqueue 메서드를 통해 요소를 삽입하고, dequeue 메서드를 통해 우선순위가 가장 높은 요소를 제거할 수 있습니다.

마치며

우선순위 큐는 많은 알고리즘 및 데이터 구조에서 사용되며, 자바스크립트를 비롯한 다양한 언어에서 구현 및 활용됩니다. 이를 통해 데이터를 우선순위에 따라 처리하는 데 유용하게 활용할 수 있습니다.

참고문헌: