PriorityQueue모듈과 heapq모듈

우선순위 큐

FIFO의 구조를 갖는 기본 큐와 달리 우선순위가 높은 데이터가 먼저 나오는 큐

---

PriorityQueue 모듈

기본 정렬 : 오름차순
내부적으로 heapq를 사용함

함수 및 시간 복잡도

• put(data) : 데이터 삽입, O(logN)
• get() : 데이터 삭제 및 반환, O(logN)

사용법

import queue.PriorityQueue class

from queue import PriorityQueue

q = PriorityQueue()

q.put(10)
q.put(20)
q.put(5)

print(q.get())	# 5
print(q.get())	# 10
print(q.get())	# 20

---

heapq 모듈

기본 정렬: 오름차순

함수 및 시간 복잡도

• heapify(list) : 리스트를 heapq로 변환, O(logN)
• heappush(heap, data) : heap에 데이터를 삽입, O(logN)
• heappop(heap) : heap에서 데이터를 삭제 및 반환, O(logN)

사용법

import heapq

import heapq

lst = [5, 4, 1, 3, 2]
heap.heapify(lst)	# lst를 heapq로 바꿔주는 함수

heap.heappush(lst, 10)
heap.heappush(lst, -10)

print(heap.heappop(lst))	# -10
print(heap.heappop(lst))	# 1
print(heap.heappop(lst))	# 2

heapq를 내림차순으로 만드는 법

heapq에 데이터를 넣을 때 -n으로 넣거나, (-n, n)을 넣어서 -n을 기준으로 정렬하도록 한다.

heapify 활용

from heapq import heapify

q = [10, 5, 20, 15]
heapify([-i for i in q])

튜플 활용

from heapq import heappush

q = [10, 5, 20, 15]
max_heap = []
for i in q:
	heappush(q, (-i, i))

---

PriorityQueue와 heapq의 차이점

PriorityQueue 모듈이 내부적으로 heapq를 사용하기 때문에 크게 다른 점은 없으나,
PriorityQueue는 thread-safe하고 heapq는 non-safe하다는 것이 차이점이다.

따라서 thread-safe할 필요가 없다면 heapq를 사용하는 것이 좋다.
코딩테스트에서는 heapq를 사용하는 것이 시간적 측면에서 유리하다.

참고

• stackoverflow - what's the difference between heapq and PriorityQueue in python?
• thread-safe란?