[Python] 우선순위 큐 (Priority Queue) 개념 정리 및 예제

우선순위 큐(Priority Queue) 란? 

• 데이터의 '우선순위'에 따라 데이터를 관리하는 자료구조
• '큐(Queue)'라는 자료구조를 확장한 개념
• 단순히 데이터를 선입선출(FIFO, First In First Out)하는 방식 대신 데이터마다 설정된 '우선순위'에 따라 데이터의 순서가 정해지는 점이 큐와 다름

이해하기 쉽게 예를 들면, 병원의 응급실에서 환자를 처리하는 방식을 생각해 볼 수 있다. 응급실에선 누가 먼저 왔는지 보다는 환자의 상태가 얼마나 심각한지에 따라 순서가 결정된다. 즉, 상황이 급하거나 중요한 환자가 먼저 치료를 받게 된다. 이처럼 '긴급성'이라는 우선순위에 따라 환자의 치료 순서가 정해지는 것이 우선순위 큐와 유사하다.

 

우선순위 큐(Priority Queue) 사용

파이썬에서 우선순위 큐를 'heapq' 모듈을 통해 사용할 수 있다. 
우선순위 큐를 활용한 간단한 예시이다, 

import heapq

# 우선순위 큐를 위한 빈 리스트 생성
priority_queue = []

# 튜플 (우선순위, 데이터) 형식으로 데이터 추가
heapq.heappush(priority_queue, (3, "Apple"))
heapq.heappush(priority_queue, (1, "Banana"))
heapq.heappush(priority_queue, (2, "Cherry"))

# 우선순위가 가장 높은 데이터부터 추출
while priority_queue:
    priority, data = heapq.heappop(priority_queue)
    print(priority, data)

 

파이썬의 'heapq' 모듈에서는 튜플의 첫 번째 원소를 우선순위로 간주하고 이를 기반으로 힙을 구성한다. 

1 Banana
2 Cherry
3 Apple

코드를 실행하면 다음과 같은 출력을 얻을 수 있다. 

우선순위 큐는 데이터가 추가될 때마다 자동으로 정렬되므로, 데이터를 추출할 때는 항상 우선순위가 가장 높은 데이터로부터 추출된다. 위의 예시에서는 "Banana"가 가장 높은 우선순위(1)를 가지므로 가장 먼저 추출된다.