[Python] Priority Queue, heapq의 차이점

 

자료구조 시간에 heap은 Priority Queue라고 배웠습니다.

그럼 파이썬 라이브러리에서는 2개 다 존재하는데 이 차이점은 뭘까?

 

<Python 3.10의 Priority Queue 내부로직>

내부로직은 heapq를 사용하고 있었다.

그럼 차이점은 뭘까?

 

https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python

What's the difference between heapq and PriorityQueue in python?

스택오버플로우의 올라온 글을 참고하여 작성합니다.

---

<요약>

• PriorityQueue: Thread-Safe 하다.
• heapq: Thread-Non-Safe 하다.

 

두 개의 차이점은 아래글을 참고해 주세요.

https://codewizard.tistory.com/52

[Python] GIL과 thread-safe, Thread-Non-Safe

---

<결론>

멀티스레드가 사용하는 과정 속에서 Thread-Safe가 필요한 상황이라면 

Priority Queue를 사용하고 코딩테스트 같은 단일스레드문제에서는 heapq를 사용한다.

(※ Priority Queue는 Thread-Safe를 하기 위해 검증절차를 거치기 때문에 trade off로 느려지기 때문이다.)

---

 

# 추가의문: 그럼 Priority Queue는 언제 사용할까?

큐는 멀티(스레드, 프로세스)에서 어떤 대기열을 구현하기 위해 사용할 수 있는데

이때 여러 스레드 간에 정보를 훼손하지 않고 교환해야 한다.

이때 Thread-Safe가 되어야 하므로 locking이 제공되는 Priority Queue사용.

---

# priorityQueue와 heapq의 차이점 

• priorityQueue는 클래스 이므로 import 하고 변수에 pq = priorityQueue()로 객체 생성한 후 사용.
• but heapq는 모듈이기에 기본 자료형인 리스트를 이용하여 사용하면 된다.