파이썬 PriorityQueue vs heapq 속도 분석

가운데를 말해요 문제를 풀던 도중 시간 초과의 이유를 모르겠어서 정답을 봤는데 heapq로 푼걸 확인할 수 있었다.

내가 사용한 라이브러리는 PriorityQueue였는데, 직접 속도 차이를 비교해봤다.

from queue import PriorityQueue
import heapq
import time
import random
N = 100000
arr = [random.randint(1, 1000) for _ in range(N)]
minq = PriorityQueue()
for x in arr:
    minq.put((x, x))
start = time.time()
while not minq.empty():
    minq.get()
end = time.time()
print("Priority Queue:", end-start)
start = time.time()
while len(arr):
    heapq.heappop(arr)
end = time.time()
print("Heap:", end-start)
'''
Priority Queue: 0.5937907695770264
Heap: 0.0937814712524414
'''

왜 이렇게 시간 차이가 나는지 이유를 찾아봤는데, 스택오버플로에서 답을 들을 수 있었다.

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

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

요약하자면 heapq를 래핑해서 멀티쓰레드 환경에서도 돌아갈 수 있도록 처리해놓아서 오버헤드가 걸린다.