[Algorithm] Priority Queue (우선순위 큐)

우선순위 큐(Priority Queue)

우선순위 큐는 가장 중요한(우선순위가 높은) 요소가 먼저 처리되는 자료구조

→   일반적인 큐(Queue)는 선입선출(FIFO, First In First Out)

→   우선순위 큐는 우선순위가 높은 요소가 먼저 나오는 구조

 

 

---

특징

• 자동 정렬
  • 요소를 삽입할 때마다 내부적으로 정렬하고 꺼낼 때 항상 최우선 요소가 반환된다.
• 힙(Heap) 자료구조 활용
  • 일반적으로 이진 힙(Binary Heap)을 사용하여 O(logN)의 시간복잡도로 삽입/삭제 가능
• 최소 힙(Min Heap) / 최대 힙(Max Heap)
  • 최소 힙(Min Heap, default)  :  값이 작은 요소가 먼저 반환된다.
  • 최대 힙(Max Heap)  :  값이 큰 요소가 먼저 반환된다.

 

 

---

Python heapq 모듈

Python에서 heapq 모듈을 사용하여 우선순위 큐를 구현할 수 있다.

 

 

최소 힙(Min Heap)

import heapq

pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)
heapq.heappush(pq, 1)

# pq = [8, 5, 2, 1]
print(heapq.heappop(pq))  # 1
# pq = [8, 5, 2]
print(heapq.heappop(pq))  # 2
# pq = [8, 5]
print(heapq.heappop(pq))  # 5

 

 

최대 힙(Max Heap)

heapq는 최소 힙만 지원하기 때문에 최대 힙을 구현하려면 음수 변환을 활용해야 한다.

import heapq

pq = []
heapq.heappush(pq, -5)  # 음수로 변환
heapq.heappush(pq, -2)
heapq.heappush(pq, -8)
heapq.heappush(pq, -1)

# pq = [-1, -2, -5, -8]
print(-heapq.heappop(pq))  # 8
# pq = [-1, -2, -5]
print(-heapq.heappop(pq))  # 5
# pq = [-1, -2]
print(-heapq.heappop(pq))  # 2

 

 

---

우선순위 큐 예시

 

1.  최적화 문제

• 우선순위 큐는 최단 경로 문제를 해결하는 다익스트라 알고리즘에서 활용된다.
• 각 정점까지의 최단 거리를 우선순위 큐로 관리하여 가장 작은 거리부터 처리하는 방식

import heapq

pq = []
heapq.heappush(pq, (0, "A"))  # (거리, 노드)
heapq.heappush(pq, (2, "B"))
heapq.heappush(pq, (1, "C"))

print(heapq.heappop(pq))  # (0, "A") → 가장 가까운 노드가 먼저 탐색됨
print(heapq.heappop(pq))  # (1, "C")

'''가장 짧은 거리부터 탐색하여 경로를 최적화하는 데 사용된다.'''

 

 

 

2.  정렬되지 않은 데이터에서 최대/최솟값 찾기

• 우선순위 큐는 실시간으로 정렬된 데이터를 유지하는 데 유용하다.

import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
pq = []

for num in nums:
    heapq.heappush(pq, num)
    if len(pq) > 3:  # 가장 큰 3개만 유지
        heapq.heappop(pq)

print(pq)  # [5, 6, 9] (가장 큰 3개)

'''실시간으로 가장 큰 K개 요소만 유지하는 문제에 활용 가능'''