5. Priority Queue - 파이썬 우선순위큐 공부하기

우선순위 큐

• 우선순위가 가장 높은 요소가 먼저 추출되는 자료형 
• 최댓값/최솟값 추출
• 일반적인 큐와 달리 데이터를 꺼낼 때 우선순위를 갖는 큐값이 입력되고 삭제될 때마다 자료구조가 내부적으로 정렬해줘야 하기 때문에 구현방법과 시간 복잡도에 차이가 있다.

 

 

구현방법

• 리스트 또는 힙을 이용

자료형	삽입	삭제
리스트	O(1)	O(n)
힙	O(logn)	O(logn)
우선순위 큐 (힙이용)	O(logn)	O(logn)

 

파이썬에서 큐 사용법

queue 모듈을 사용한다. 이 모듈은 내부적으로 heapq 모듈을 사용한다.

from queue import PriorityQueue

que = PriorityQueue() # 내부적으로 heap 모듈을 사용
limitedQue = PriorityQueue(maxsize=10) #크기 제한이 있는 우선순위 큐

# 원소 삽입
que.put(item)
que.put(1)
que.put(2)
que.put((priority, item)) # (우선순위, 아이템) 튜플 형태로 삽입이 가능

# 원소 삭제
print(que.get())

 

반전!

하지만, 파이썬에서 우선순위큐를 구현할 때에는 heapq 모듈을 직접적으로 사용하는 것이 좋다.
이유 : 5. 파이썬 PriorityQueue vs heapq (tistory.com)