PriorityQueue

파이썬의 PriorityQueue는 Queue와 같이 FIFO(First In First Out) 방법을 가지고 있고 내부적으로 데이터를 정렬된 상태로 보관하는 자료구조입니다. 이는 heapq 모듈을 통해 구현되어 있습니다.

import

queue 내장 모듈 내 PriorityQueue 클래스를 import하여 사용합니다.

from queue import PriorityQueue

PriorityQueue 생성

PriorityQueue() 생성자를 사용하여 PriorityQueue를 초기화합니다.

pque = PriorityQueue()

PriorityQueue의 최대 크기를 설정해주고 싶다면 maxsize를 넣어줍니다.

pque = PriorityQueue(maxsize=10)

데이터 삽입

PriorityQueue 클래스의 put() 메서드를 사용하여 데이터를 삽입합니다.

pque.put(1)
pque.put(3)
pque.put(2)
pque.put(5)
pque.put(4)

데이터 삭제

PriorityQueue 클래스의 get() 메서드를 사용하여 데이터를 삭제합니다.

# 위의 삽입 순서와 다르게 오름차순 정렬(default)되어 있기 때문에 작은 값 순으로 삭제됩니다.
pque.get() # 1
pque.get() # 2
pque.get() # 3

내부 정렬 기준 설정

default로 설정되어있는 오름차순이 아닌 다른 기준으로 데이터를 정렬시키려면
(우선순위, 데이터)의 튜플 형식으로 데이터를 추가하고 제거합니다.

pque.put((1, '첫번째'))
pque.put((4, '네번째'))
pque.put((3, '세번째'))
pque.put((5, '다섯번째'))
pque.put((2, '두번째'))

print(que.get()[1])  # 첫번째
print(que.get()[1])  # 두번째
print(que.get()[1])  # 세번째

기타 메소드

pque.qsize() # PriorityQueue의 크기 반환
pque.empty() # PriorityQueue가 비어있는지의 여부 반환
pque.full() # PriorityQueue가 꽉 찼는지의 여부 반환

시간복잡도

파이썬의 PriorityQueue는 heap 구조를 통해 구현되어있어 put(), get() 메소드는 O(logN)의 시간 복잡도를 가집니다.