[알고리즘이론] 우선순위 큐(Priority Queue) 파이썬으로 구현하기

파이썬에서 우선순위 큐(Priority Queue)는 heapq 모듈을 이용하여 구현할 수 있습니다. heapq 모듈은 이진 힙(binary heap) 자료구조를 제공하며, 우선순위 큐는 이진 힙을 이용하여 구현됩니다.

 

이진 힙은 완전 이진 트리(complete binary tree)의 일종으로, 최솟값 혹은 최댓값을 빠르게 찾기 위해 구현된 자료구조입니다. 파이썬의 heapq 모듈은 기본적으로 최소힙(min heap)을 제공합니다. 따라서 최소값을 빠르게 찾을 수 있습니다. 최대값을 찾으려면 입력된 값에 대한 음수를 취하여 최소값을 찾은 후, 다시 음수를 취하는 방법으로 최대값을 구할 수 있습니다.

 

다음은 heapq 모듈을 이용하여 우선순위 큐를 구현한 예제입니다.

 

import heapq

pq = []  # 우선순위 큐 생성
heapq.heappush(pq, 3)  # 3 추가
heapq.heappush(pq, 1)  # 1 추가
heapq.heappush(pq, 4)  # 4 추가
heapq.heappush(pq, 1)  # 1 추가
while pq:
    print(heapq.heappop(pq))  # 출력: 1 1 3 4

 

위 코드에서 heapq.heappush(pq, x)는 우선순위 큐 pq에 원소 x를 추가합니다. heapq.heappop(pq)는 우선순위 큐 pq에서 최소값을 제거하고 반환합니다. 따라서 while 루프에서는 최소값부터 차례대로 출력됩니다. 이 예제는 출력 결과가 [1, 1, 3, 4]로 예상한 대로 최소값부터 차례대로 출력됩니다.

 

우선순위 큐에서는 일반적으로 우선순위가 높은 원소를 먼저 처리하는 것이 중요합니다. 따라서 heapq.heappush(pq, x)에서 x는 일반적으로 (우선순위, 값)의 형태로 입력됩니다. heapq.heappop(pq)를 호출할 때는 최소값인 (우선순위, 값)의 형태로 반환됩니다. 이렇게 하면 우선순위가 높은 값이 먼저 처리되는 것이 보장됩니다.

 

heapq.heappush(pq, (3, 'task3'))와 같이 (우선순위, 값)의 형태로 값을 추가할 수 있습니다. 위 예제에서는 우선순위가 3인 'task3'을 추가합니다.

 

import heapq

pq = []
heapq.heappush(pq, (3, 'task3'))  # 우선순위 3, 값 'task3' 추가
heapq.heappush(pq, (1, 'task1'))  # 우선순위 1, 값 'task1' 추가
heapq.heappush(pq, (4, 'task4'))  # 우선순위 4, 값 'task4' 추가
heapq.heappush(pq, (1, 'task2'))  # 우선순위 1, 값 'task2' 추가
while pq:
    print(heapq.heappop(pq))  # 출력: (1, 'task1') (1, 'task2') (3, 'task3') (4, 'task4')

 

위 예제에서는 while 루프에서 heapq.heappop(pq)를 호출하여 최소값부터 차례대로 출력합니다. 따라서 출력 결과는 (1, 'task1'), (1, 'task2'), (3, 'task3'), (4, 'task4')의 순서로 출력됩니다.

 

heapq 모듈은 이진 힙을 이용하여 우선순위 큐를 구현하므로, 시간복잡도는 O(log n)입니다. 따라서 대부분의 상황에서 효율적으로 동작합니다.