[Python] 우선순위 큐 (PriorityQueue)

PriorityQueue는 heapq를 사용해 구현되어 있다.

#cpython/Lib/queue.py

from heapq import heappush, heappop

class PriorityQueue(Queue):
    '''Variant of Queue that retrieves open entries in priority order (lowest first).

    Entries are typically tuples of the form:  (priority number, data).
    '''

    def _init(self, maxsize):
        self.queue = []

    def _qsize(self):
        return len(self.queue)

    def _put(self, item):
        heappush(self.queue, item)

    def _get(self):
        return heappop(self.queue)

 

그럼 heapq와 차이점은 무엇일까?

priorityqueue는 thread safe를 보장하지만 heapq는  thread safe를 보장하지 않는다는 점이다.

파이썬은 GIL의 특성상 멀티 스레딩이 거의 의미가 없기 때문에 대부분 멀티 프로세싱으로 활용한다는 점을 생각해보면, PriorityQueue 모듈의 멀티 스레딩 자원은 사실 큰 의미는 없다.

또한 thread safe를 보장한다는 얘기는 내부적으로 Locking을 제공한다는 의미이므로 Locking Overhead가 발생해 성능에 영향을 끼친다.

따라서 굳이 multithread로 구현할 게 아니라면 PriorityQyeye 모듈은 사용할 필요가 없다.

또한 실무에서도 우선순위 큐는 대부분 heapq로 구현하고 있다.

PriorityQueue 사용법

from queue import 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() 메서드는 삭제된 원소를 리턴하기 때문에, 위와 같이 출력을 해보면, 크기 순서대로 원소가 삭제됨을 알 수 있습니다.

 

참고: https://www.daleseo.com/python-priority-queue/,
https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python,
https://slowsure.tistory.com/130