[Python] 우선순위 큐(PriorityQueue) 사용 방법

 

 

 

 

 

 

🌈 파이썬 우선순위 큐(PriorityQueue) 사용 방법

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

 

즉, 우선순위 큐의 내부에는 데이터를 정렬된 상태로 보관하는 로직이 있으며 heapq 모듈을 통해 구현되어 있다. 따라서 우선순위 큐의 put(), get() 메서드는 O(log n)의 시간 복잡도를 가진다.

 

(리스트는 삽입 O(1) 삭제 O(N)의 복잡도를 가지지만, 힙은 삽입, 삭제 모두 O(logN)의 복잡도를 가지기 때문이다.)

 

 

 

1️⃣ 클래스 임포트 및 선언

PriorityQueue 클래스는 queue 내장 모듈에서 제공하기 때문에 라이브러리 설치 없이 사용할 수 있다.

from queue import PriorityQueue
queue = PriorityQueue()

 

또한, 우선순위 큐는 사이즈에 제한이 없기 때문에, 사이즈에 제한을 두고 싶다면 아래와 같이 선언한다.

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

 

 

 

2️⃣ 원소 추가

PriorityQueue 클래스의 put() 메서드를 이용하여 우선순위 큐에 원소를 추가할 수 있다.

from queue import PriorityQueue
queue = PriorityQueue()
queue.put(4)
queue.put(8)
queue.put(6)
queue.put(10)
queue.put(2)

 

 

 

3️⃣ 원소 제거(=반환)

PriorityQueue 클래스의 get() 메서드를 이용하여 우선순위 큐에 원소를 제거(=반환)할 수 있다.

또한, 우선순위 큐는 값을 오름차순으로 반환하는 특성이 있기 때문에 아래와 같은 순서로 반환한다.

from queue import PriorityQueue
queue = PriorityQueue()
queue.put(4)
queue.put(8)
queue.put(6)
queue.put(10)
queue.put(2)

print(queue.get())  # 2
print(queue.get())  # 4
print(queue.get())  # 6
print(queue.get())  # 8
print(queue.get())  # 10

 

만약 위의 결과를 역순으로 반환하고 싶다면 튜플 형태로 값을 put 하여 반환받으면 된다.

from queue import PriorityQueue
queue = PriorityQueue()
queue.put((-4, 4))
queue.put((-8, 8))
queue.put((-6, 6))
queue.put((-10, 10))
queue.put((-2, 2))

print(queue.get()[1]) # 10
print(queue.get()[1]) # 8
print(queue.get()[1]) # 6
print(queue.get()[1]) # 4
print(queue.get()[1]) # 2

 

 

 

4️⃣ 기타 메서드

 

◾ 우선순위 큐의 크기(=사이즈) 확인

우선순위 큐에는 len( ) 메서드를 사용할 수 없기 때문에 크기 확인을 위해서는 qsize( )를 사용한다.

from queue import PriorityQueue
queue = PriorityQueue()
queue.put('Apple')
queue.put('Banana')
queue.put('Cherry')
print(queue.qsize()) # 3

 

◾ 우선순위 큐가 비었는지 확인

우선순위 큐에 원소가 들어있는지 확인하기 위해서 empty( ) 메서드를 사용한다.

원소가 하나라도 존재할 경우 False를 반환하며, 원소가 존재하지 않을 경우에는 True를 반환한다.

from queue import PriorityQueue
queue = PriorityQueue()
queue.put('Temp')
print(queue.empty()) # False

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

 

◾ 우선순위 큐가 가득 찼는지 확인

우선순위 큐의 사이즈가 가득 찼는지 확인하기 위해서 full( ) 메서드를 사용한다.

원소의 개수가 maxsize와 일치할 경우 True를 반환하며, 일치하지 않으면 False를 반환한다.

from queue import PriorityQueue
queue = PriorityQueue(maxsize=1)
queue.put('Temp')
print(queue.full()) # True

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