자료구조와 알고리즘, Tree, Priority Queue

 

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지는 데이터 구조로, 일반적인 큐와 달리 요소들이 우선순위에 따라 제거됩니다. 우선순위 큐는 큐의 일종이지만, 요소를 삽입할 때 그 우선순위에 따라 적절한 위치에 배치하고, 제거할 때는 가장 높은(또는 낮은) 우선순위를 가진 요소를 먼저 제거합니다.

우선순위 큐의 특징

1. 우선순위에 따른 요소 관리: 각 요소는 우선순위를 가지고 있으며, 큐의 요소는 우선순위에 따라 정렬됩니다.
2. 삽입 및 제거: 삽입 연산과 제거 연산은 모두 우선순위를 고려하여 수행됩니다.
3. 응용 분야: 작업 스케줄링, 네트워크 트래픽 관리, 시뮬레이션 시스템 등에서 자주 사용됩니다.

구현 방법

우선순위 큐는 다양한 방법으로 구현할 수 있지만, 가장 효율적인 방법은 힙(heap) 자료구조를 사용하는 것입니다. 힙을 사용하면 삽입과 삭제 연산을 O(log n) 시간 복잡도로 수행할 수 있습니다.

배열을 사용한 간단한 구현

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

  enqueue(value, priority) {
    this.values.push({ value, priority });
    this.sort();
  }

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

  sort() {
    this.values.sort((a, b) => a.priority - b.priority); // 우선순위가 낮은 순서대로 정렬
  }
}

// 사용 예시
let pq = new PriorityQueue();
pq.enqueue("low priority task", 5);
pq.enqueue("medium priority task", 3);
pq.enqueue("high priority task", 1);

console.log(pq.values); // [{value: "high priority task", priority: 1}, {value: "medium priority task", priority: 3}, {value: "low priority task", priority: 5}]
console.log(pq.dequeue()); // {value: "high priority task", priority: 1}

위의 구현은 배열을 사용하여 요소를 정렬합니다. 그러나 이 방식은 정렬하는 데 O(n log n)의 시간이 소요되므로, 더 효율적인 방법은 힙을 사용하는 것입니다.

힙을 사용한 우선순위 큐 구현 (자바스크립트 예제)

• 최소 힙을 바탕으로 구현된 우선순위 큐
• 기존 이진 힙을 구현할 때와의 차이점은 priority 를 바탕으로 값을 넣어준다는 점입니다

class Node {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
  }
}

class PriorityQueue {
  // Write a Min Binary Heap = lower number means higher priority
  // Each Node has a value and a priority. Use the priority to build the heap
  // Enqueue method accepts a value and priority, makes a new node, and puts it in the right spot based off its prioirty
  // Dequeue method removes root element, returns it, and rearranges heap using priority

  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    this.bubbleUp();
  }
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element.priority >= parent.priority) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
  dequeue() {
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return min;
  }
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild.priority < element.priority) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild.priority < element.priority) ||
          (swap !== null && rightChild.priority < leftChild.priority)
        ) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

let ER = new PriorityQueue();

ER.enqueue('common cold', 5);
ER.enqueue('gunshot wound', 1);
ER.enqueue('high fever', 4);
ER.enqueue('broken arm', 2);
ER.enqueue('glass in foot', 3);

console.log('ER:', ER.dequeue());
console.log('ER:', ER.dequeue());
console.log('ER:', ER.dequeue());
console.log('ER:', ER.dequeue());
console.log('ER:', ER.dequeue());

우선순위 큐의 응용

1. 작업 스케줄링: 우선순위가 높은 작업을 먼저 처리해야 할 때 사용합니다.
2. 다익스트라 알고리즘: 그래프에서 최단 경로를 찾는 알고리즘에 사용됩니다.
3. 이벤트 관리 시스템: 이벤트를 우선순위에 따라 처리할 때 사용됩니다.
4. 네트워크 트래픽 관리: 데이터 패킷의 우선순위를 정해 전송 순서를 결정할 때 사용됩니다.

우선순위 큐는 여러 가지 문제를 효율적으로 해결하는 데 유용한 자료 구조입니다. 특히, 힙을 사용하여 구현하면 삽입과 삭제 연산을 효율적으로 수행할 수 있어 다양한 응용 분야에서 활용됩니다.