Priority Queue는 일반 Queue와 어떻게 다른가요?

Priority Queue는 먼저 들어온 순서가 아니라 우선순위가 높은 요소를 먼저 꺼내는 큐입니다. 일반 Queue가 FIFO 규칙을 따르는 데 비해, Priority Queue는 작업의 중요도, 비용, 거리 같은 기준으로 처리 순서를 결정합니다.

핵심 개념

• 일반 큐는 enqueue 순서를 보존하고 dequeue는 가장 오래된 요소를 반환합니다.
• Priority Queue는 dequeue 시 최솟값 또는 최댓값 우선순위 요소를 반환합니다.
• 대개 Heap으로 구현해 삽입과 추출을 O(log n)에 처리합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

일반 Queue
enqueue: A(낮음), B(높음), C(중간)
dequeue: A -> B -> C

Priority Queue
enqueue: A(3), B(1), C(2)  // 숫자가 작을수록 높은 우선순위
dequeue: B -> C -> A

const jobs = [
  { name: 'email', priority: 3 },
  { name: 'payment', priority: 1 },
  { name: 'report', priority: 5 },
];
// 실무에서는 heap 기반 priority queue로 가장 높은 우선순위 작업부터 처리

실무에서 주의할 점

• 낮은 우선순위 작업이 계속 밀리는 starvation이 생길 수 있습니다.
• 우선순위가 같은 작업의 처리 순서를 보장하려면 sequence number가 필요합니다.
• 우선순위가 자주 변하는 경우 decrease-key 지원 여부가 중요합니다.

실무 적용 가이드

• 스케줄러, 다익스트라, A* 탐색, 작업 큐에서 사용합니다.
• 장시간 대기한 작업의 우선순위를 올리는 aging 전략으로 starvation을 줄일 수 있습니다.
• 업무 시스템에서는 우선순위 기준이 공정하고 설명 가능해야 합니다.

함께 연결해서 보면 좋은 키워드

Priority Queue, Heap, Scheduler, Dijkstra, Starvation

정리

Priority Queue는 먼저 들어온 순서가 아니라 우선순위가 높은 요소를 먼저 꺼내는 큐입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.