우선순위 큐(Priority Queue)란?

우선순위 큐는 큐처럼 데이터를 저장하지만, 꺼낼 때는 순서가 아니라 "우선순위(Priority)"에 따라 꺼냄

즉, 먼저 들어왔다고 나간다 X
중요한 놈(우선순위가 높은 놈)이 먼저 나감 !

일반 큐와의 차이는 ?

예제 상황으로 보자

우선순위 큐에 다음 작업이 있다고 가정해보자

작업 A - 우선순위 3  
작업 B - 우선순위 1  
작업 C - 우선순위 2

enqueue() 순서는 A → B → C
하지만 dequeue() 하면:

1. 작업 B (우선순위 1)

2. 작업 C (우선순위 2)

3. 작업 A (우선순위 3)

→ 우선순위 높은 놈부터 먼저 꺼낸다.

Python 구현 (heapq 사용)

import heapq

pq = []
heapq.heappush(pq, (3, "A"))  # (우선순위, 값)
heapq.heappush(pq, (1, "B"))
heapq.heappush(pq, (2, "C"))

while pq:
    priority, task = heapq.heappop(pq)
    print(f"{task} (우선순위 {priority})")

출력

B (우선순위 1)
C (우선순위 2)
A (우선순위 3)

우선순위 큐의 내부 구현

힙(Heap) 자료구조를 사용

대표적으로 이진 최소 힙(Min Heap)
→ 부모 노드 ≤ 자식 노드 → 루트에는 항상 최우선 요소

🔧 시간 복잡도

• 삽입 (push): O(log n)

• 제거 (pop): O(log n)

• peek (확인): O(1)

실제 사용 예

• 운영체제 : CPU 스케쥴링 [ 더 급한 작업을 먼저 처리 ]

• 네트워크 : 패킷 우선 처리 [ 실시간 데이터 우선 전송 ]

• 알고리즘 : 다익스트라 최단경로, A* 탐색, 허프만 인코딩 등