우선순위 큐

우선순위 큐(priority queue)는 일반적인 큐와 달리, 삽입된 요소 중 우선순위(priority)가 가장 높은 요소를 먼저 꺼내는 자료 구조이다. 기본적인 큐의 선입선출(FIFO) 원칙을 따르지 않고, 우선순위에 따라 데이터를 처리한다.

1 개요

우선순위 큐는 각 요소에 우선순위를 부여하여, 데이터가 삽입된 순서와 무관하게 우선순위가 높은 데이터가 먼저 처리되도록 한다. 일반적으로 최소 힙(min-heap) 또는 최대 힙(max-heap) 자료 구조를 이용해 구현된다.

2 주요 연산

• 삽입(Enqueue)
  • 새 요소를 우선순위와 함께 큐에 추가한다.
• 삭제(Dequeue)
  • 우선순위가 가장 높은(또는 가장 낮은) 요소를 큐에서 제거하고 반환한다.
• Peek
  • 큐에서 우선순위가 가장 높은 요소를 제거하지 않고 확인한다.

3 특징

• 선입선출(FIFO) 대신 우선순위순으로 요소를 처리한다.
• 삽입과 삭제 연산은 힙(Heap) 자료 구조를 이용하면 효율적으로 O(log n)에 수행할 수 있다.
• 일반 배열이나 정렬된 리스트로도 구현할 수 있으나, 힙을 이용하는 것이 성능 면에서 우수하다.

4 구현 방법

• 배열 기반
  • 삽입 시 단순 추가하고, 삭제 시 가장 높은 우선순위를 선형 탐색하여 제거 (비효율적).
• 정렬된 배열/리스트
  • 삽입 시 정렬을 유지하여 추가, 삭제는 맨 앞 요소를 제거.
• 힙(Heap) 구조
  • 삽입과 삭제 모두 O(log n) 시간 복잡도로 처리할 수 있어 가장 일반적이다.

5 활용 예시

• 작업 스케줄링(높은 우선순위 작업을 먼저 처리)
• 네트워크 패킷 우선 전송
• 다익스트라 알고리즘(최단 경로 탐색)
• 이벤트 기반 시뮬레이션

6 간단한 구현 예시

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def enqueue(self, priority, item):
        heapq.heappush(self.heap, (priority, item))

    def dequeue(self):
        if self.heap:
            return heapq.heappop(self.heap)[1]
        raise IndexError("dequeue from empty priority queue")

    def peek(self):
        if self.heap:
            return self.heap[0][1]
        raise IndexError("peek from empty priority queue")

# 사용 예시
pq = PriorityQueue()
pq.enqueue(2, "Task A")
pq.enqueue(1, "Task B")
pq.enqueue(3, "Task C")

print(pq.dequeue())  # 출력: Task B (우선순위 1)
print(pq.dequeue())  # 출력: Task A (우선순위 2)

7 우선순위 큐와 일반 큐의 차이

• 일반 큐: 삽입 순서대로 요소를 처리 (FIFO).
• 우선순위 큐: 우선순위가 높은 요소를 먼저 처리.

8 같이 보기

• 힙
• 큐
• 다익스트라 알고리즘
• 힙 정렬

9 참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.