파이썬의 우선순위 큐(PriorityQueue) 사용법

데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 PriorityQueue(우선순위 큐)에 대해서 알아보겠습니다.

우선순위 큐 자료구조

우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다. 이 말은 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 있다는 뜻이고, 좀 더 구체적으로 얘기하면 heapq 모듈을 통해 구현되어 있습니다.

파이썬의 heapq에 대한 자세한 설명은 관련 포스팅, 파이썬의 heapq 모듈로 힙 자료구조 사용하기을 참조바랍니다.

클래스 임포트

우선 PriorityQueue 클래스는 queue 내장 모듈에서 제공되기 때문에 파이썬만 설치되어 있으면 별다른 추가 설치없이 임포트할 수 있습니다.

from queue import PriorityQueue

우선순위 큐 생성

PriorityQueue() 생성자를 이용해서 비어있는 우선순위 큐를 초기화할 수 있습니다.

que = PriorityQueue()

우선순위 큐의 디폴트 사이즈는 무한대입니다. 만약에 특정 최대 크기를 가진 우선순위 큐가 필요하다면 maxsize를 넘기면 됩니다.

que = PriorityQueue(maxsize=8)

우선순위 큐에 원소 추가

PriorityQueue 클래스의 put() 메서드를 이용하여 우선순위 큐에 원소를 추가할 수 있습니다.

que.put(4)
que.put(1)
que.put(7)
que.put(3)

우선순위 큐에 원소 삭제

PriorityQueue 클래스의 get() 메서드를 이용하여 우선순위 큐에 원소를 삭제할 수 있습니다.

print(que.get())  # 1
print(que.get())  # 3
print(que.get())  # 4
print(que.get())  # 7

get() 메서드는 삭제된 원소를 리턴하기 때문에, 위와 같이 출력을 해보면, 크기 순서대로 원소가 삭제됨을 알 수 있습니다.

정렬 기준 변경

만약 단순 오름차순이 아닌 다른 기준으로 원소가 정렬되기를 원한다면, (우선순위, 값)의 튜플의 형태로 데이터를 추가하고 제거하면 됩니다.

que.put((3, 'Apple'))
que.put((1, 'Banana'))
que.put((2, 'Cherry'))

print(que.get()[1])  # Banana
print(que.get()[1])  # Cherry
print(que.get()[1])  # Apple

마치면서

지금까지 파이썬의 내장 자료구조인 우선순위 큐(PriorityQueue)를 사용하는 방법에 대해서 알아보았습니다. 참고로, 내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n)의 시간 복잡도를 가집니다.