우선순위 큐 (Priority Queue)

1. 우선순위 큐란?

일반적인 큐는 먼저 들어온 데이터가 먼저 나가는 구조(FIFO)지만,
우선순위 큐는 "우선순위가 높은 데이터"를 먼저 꺼내는 자료구조입니다.

Python에서는 heapq 모듈을 사용해 구현하며, 내부적으로 힙(Heap) 자료구조를 기반으로 합니다.

---

2. 우선순위 큐 사용 예시

사용 목적	설명
최솟값/최댓값 추출	정렬 없이 즉시 꺼낼 수 있음
최단 경로 알고리즘	다익스트라, 프림 등에서 활용
실시간 작업 처리	우선순위 높은 작업 먼저 수행
이벤트 처리 시뮬레이션	시간순 혹은 조건순으로 정렬 유지

---

3. Python에서의 구현

Python의 heapq는 기본적으로 최소 힙(Min Heap) 구조입니다.

즉, 가장 작은 값을 먼저 꺼내는 구조입니다.

최소 힙 기본 사용법

import heapq

pq = []
heapq.heappush(pq, 4)
heapq.heappush(pq, 1)
heapq.heappush(pq, 7)

print(heapq.heappop(pq))  # 출력: 1 (가장 작은 값부터 나옴)

---

최대 힙으로 사용하고 싶을 때

Python에는 Max Heap이 없기 때문에, 음수로 변환하여 넣고 꺼낼 때 다시 음수로 바꿔줍니다.

python
복사편집
import heapq

pq = []
heapq.heappush(pq, -4)
heapq.heappush(pq, -1)
heapq.heappush(pq, -7)

print(-heapq.heappop(pq))  # 출력: 7 (가장 큰 값부터 나옴)

---

(우선순위, 값) 형태로 튜플 저장

import heapq

pq = []
heapq.heappush(pq, (2, 'A'))  # 우선순위 2
heapq.heappush(pq, (1, 'B'))  # 우선순위 1

print(heapq.heappop(pq))  # 출력: (1, 'B')

---

4. heapq 주요 함수 정리

함수	설명
heappush(heap, item)	item을 힙에 추가
heappop(heap)	힙에서 최소값 삭제 후 반환
heapify(list)	일반 리스트를 힙으로 변환
heapreplace(heap, item)	최소값 제거하고 item 삽입
heappushpop(heap, item)	item 삽입 후 최소값 제거
nlargest(k, iterable)	가장 큰 k개 반환
nsmallest(k, iterable)	가장 작은 k개 반환

---

5. 시간 복잡도

연산	시간 복잡도
삽입 (heappush)	O(log N)
삭제 (heappop)	O(log N)
최소값 접근	O(1)

---

6. C언어로 구현할 때 주의사항

• heapq 같은 모듈 없음 → 힙 구조 직접 구현 필요
• Max Heap은 따로 설계해야 함
• 구조체 + 비교 함수로 (우선순위, 값) 관리
• 배열을 기반으로 upheap, downheap 연산 구현 필요

---

7. 핵심 요약

• 우선순위 큐는 값의 크기(또는 조건)에 따라 꺼내는 순서가 달라지는 큐
• Python에서는 heapq로 구현 가능 (Min Heap만 지원)
• Max Heap은 음수 처리로 구현
• 알고리즘 문제에서 자주 사용됨 (특히 다익스트라, 중앙값, 이벤트 처리 등)