[Python] 우선순위 큐 (Priority Queue)

우선순위 큐 (Priority Queue)

 

우선순위 큐 (Priority Queue) 란?

데이터를 추가 (Put) 한 순서와 상관없이 데이터를 꺼낼 때 (Get) 값을 오름차순하여 반환하는 자료구조이다.

내부에는 데이터를 정렬된 상태로 보관하는 로직이 heapq 모듈을 통해 구현되어 있으며 시간 복잡도는 \(O(logN)\)을 가진다.

\(\rightarrow\) 힙 (Heap) 정리

힙 (Heap)

 

Import

PriorityQueue 클래스는 queue 내장 모듈에서 제공합니다.

from queue import PriorityQueue
queue = PriorityQueue()
# 사이즈를 제한하고 싶으면,
queue = PriorityQueue(maxsize=10)

 

Put

put() 메서드를 사용하여 PriorityQueue에 원소를 추가할 수 있습니다.

from queue import PriorityQueue
queue = PriorityQueue()

queue.put(4)
queue.put(9)
queue.put(5)
queue.put(8)

 

Get

get() 메서드를 사용하여 원소를 오름차순으로 반환할 수 있습니다.

from queue import PriorityQueue
queue = PriorityQueue()

queue.put(4)
queue.put(9)
queue.put(5)
queue.put(8)

print(queue.get()) # 4
print(queue.get()) # 5
print(queue.get()) # 8
print(queue.get()) # 9

 

만약 역순으로 반환하고 싶으면 다음과 같이 튜플 형태로 값을 put 하여 반환받으면 됩니다.

from queue import PriorityQueue
queue = PriorityQueue()

queue.put((-4, 4))
queue.put((-9, 9))
queue.put((-5, 5))
queue.put((-8, 8))

print(queue.get()[1]) # 4
print(queue.get()[1]) # 5
print(queue.get()[1]) # 8
print(queue.get()[1]) # 9

 

Size

len() 메서드를 사용할 수 없기 때문에 qsize() 메서드를 사용합니다.

from queue import PriorityQueue
queue = PriorityQueue()

queue.put(4)
queue.put(9)
queue.put(5)

print(queue.qsize())  # 3

 

Empty

큐가 비어있는지 확인하기 위해 empty() 메서드를 사용합니다.

from queue import PriorityQueue
queue = PriorityQueue()

queue.put(4)
print(queue.empty())  # False

queue.get()
print(queue.empty())  # True

 

Full

큐가 가득 찼는지 확인하기 위해 full() 메서드를 사용합니다.

from queue import PriorityQueue
queue = PriorityQueue(maxsize=2)

queue.put(4)
queue.put(1)
print(queue.full())  # True

queue.get()
print(queue.full())  # False