우선순위 큐란?

일반적인 큐는 먼저 들어온 순서대로 처리 (FIFO) 하지만,
우선순위 큐는 "우선순위가 높은 데이터"를 먼저 꺼내는 큐이다.

그냥 줄 서는 게 아니라, "급한 사람 먼저 처리" 하는 느낌이다.
예를 들어, 비상환자 → 일반환자 순서로 진료하는 병원처럼!

---

일반 큐와 차이점

구분	일반 큐 (Queue)	우선순위 큐 (Priority Queue)
처리 순서	먼저 들어온 순서 (FIFO)	우선순위가 높은 데이터 먼저
삽입 위치	항상 뒤쪽	뒤쪽 (우선순위 관계 없음)
꺼내는 위치	항상 앞쪽	가장 높은 우선순위 위치

💡 이름이 우선순위 큐 라서 큐처럼 동작할 것 이라는 생각이 들 수 있으나,
실제로는 단순히 “우선순위 값”기준으로 데이터를 꺼내는 자료구조일 뿐이다.

☑️ 우선순위 큐 동작 예시

예시)

enqueue(5)
enqueue(2)
enqueue(8)
enqueue(3)

• 일반 큐에서 꺼내면 → 5 → 2 → 8 → 3 (순서대로)
• 우선순위 큐는 꺼낼 때 → 8 → 5 → 3 → 2 (큰 수 먼저)

---

☑️ 파이썬에서 구현

1) heapq 모듈 사용 (파이썬 기본 제공)

import heapq

pq = []

# 데이터 삽입 (push)
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)
heapq.heappush(pq, 3)

# 데이터 꺼내기 (pop)
print(heapq.heappop(pq))  # 2 (기본은 '최소'가 먼저 나옴)

❗ 파이썬 heapq는 "최소 힙"

• 작은 숫자가 우선순위가 높음
• 작은 값부터 꺼냄

---

최대 힙으로 쓰려면?

• 부호를 반대로 넣으면 됨

heapq.heappush(pq, -5)  # -5는 실제로는 5 의미
heapq.heappush(pq, -2)
heapq.heappush(pq, -8)
heapq.heappush(pq, -3)

print(-heapq.heappop(pq))  # 8 출력

---

☑️ 시간복잡도

연산	시간 복잡도
삽입(push)	O(log N)
삭제(pop)	O(log N)

• 일반 큐보다 조금 느리지만 우선순위 정렬 기능 덕분에 효율적!
• 큐 | append() + pop(0) / popleft() → O(1) 만에 처리

---

☑️ 우선순위 큐 사용 예시

1) 다익스트라 알고리즘 (최단경로)

• 거리가 짧은 노드를 먼저 꺼내야 하므로 우선순위 큐 사용

2) 작업 스케줄러

• 급한 작업 먼저 처리할 때 사용

3) 시뮬레이션 문제

• 빨리 끝나는 이벤트 먼저 처리할 때 (ex: CPU 스케줄링)

---

☑️ 우선순위 큐와 heap의 관계

• 파이썬은 heapq = 우선순위 큐를 힙으로 구현한 것
• "이진 힙(Binary Heap)" 자료구조를 내부에서 사용
  → 부모 < 자식 구조로 자동 정렬됨

---

🎯 요약

개념	설명
우선순위 큐	"우선순위가 높은 데이터"를 먼저 꺼냄
파이썬 heapq	"최소 힙" 구조 (작은 값 먼저 pop)
O(log N)	삽입, 삭제 모두 효율적
최대 힙 변환	push할 때 부호를 반대로 넣어줌

---