---

우선순위 큐(Priority Queue)

---

1. 우선순위 큐란?

우선순위 큐는 각 요소에 우선순위가 부여되고, 우선순위가 높은 요소가 먼저 처리되는 추상 자료형(ADT)입니다. 일반 큐(FIFO)와 달리 요소의 추가/제거 순서가 우선순위에 의해 결정되며, 동일한 우선순위인 경우에는 삽입 순서(FIFO)를 따름

핵심 특징

• 우선순위 기반 처리: 높은 우선순위 요소가 먼저 제거됨.
• 동적 구조: 요소 추가 시마다 내부적으로 재정렬됨.
• 유연한 구현: 배열, 연결리스트, 힙(Heap) 등 다양한 자료구조로 구현 가능

---

2. 우선순위 큐의 주요 연산

// Element() : 데이터와 우선순위를 저장하기 위한 생성자 함수
function Element(data, priority) {
  this.data = data;
  this.priority = priority;
}

// PriorityQueue() : Element 관리를 위한 생성자 함수
function PriorityQueue() {
  this.array = [];
}

// getBuffer() : 객체 내 데이터 셋 반환
PriorityQueue.prototype.getBuffer = function () {
  return this.array.map((element) => element.data);
};

// isEmpty() : 객체 내 데이터 존재 여부 파악
PriorityQueue.prototype.isEmpty = function () {
  return this.array.length == 0;
};

// enqueue() : 데이터 추가
PriorityQueue.prototype.enqueue = function (data, priority) {
  let element = new Element(data, priority);
  let added = false;

  for (let i = 0; i < this.array.length; i++) {
    if (element.priority < this.array[i].priority) {
      this.array.splice(i, 0, element);
      added = true;
      break;
    }
  }

  if (!added) {
    this.array.push(element);
  }

  return this.array.length;
};

// dequeue() : 데이터 삭제
PriorityQueue.prototype.dequeue = function () {
  return this.array.shift();
};

// front() : 가장 첫 데이터 반환
PriorityQueue.prototype.front = function () {
  return this.array.length == 0 ? undefined : this.array[0].data;
};

// size() : 큐 내 데이터 개수 확인
PriorityQueue.prototype.size = function () {
  return this.array.length;
};

// clear() : 큐 초기화
PriorityQueue.prototype.clear = function () {
  this.array = [];
};

---

3. 구현 방식별 특징

구현 방식	장점	단점
정렬된 배열	peek()이 O(1)	삽입/삭제 시 O(n) 재정렬 필요
연결리스트	동적 크기 관리 용이	중간 삽입 시 탐비 시간 증가
힙(Heap)	삽입/삭제 모두 O(log n)	구현 복잡성

힙이 가장 효율적으로 널리 사용되며, Python의 queue.PriorityQueue와 Java의 PriorityQueue도 내부적으로 힙을 사용함.

---

4. 실제 활용 사례

1) 운영체제 작업 스케줄링

• 고우선순위 시스템 이벤트(예: 하드웨어 인터럽트)를 먼저 처리

2) 네트워크 패킷 관리

• VoIP 데이터(낮은 지연 요구)를 일반 데이터보다 우선 전송

3) 알고리즘 최적화

• 다익스트라 알고리즘: 최소 거리 노드 우선 처리
• A* 경로 탐색: 예상 비용이 낮은 경로 우선 탐색