알고리즘 : PriorityQueue (우선순위 큐)

요약

• 데이터를 추가한 순서대로 제거하는 Queue (큐) 와는 달리

  추가한 순서는 상관없이 제거될때 가장 작은 값을 우선순위로 제거

• 간단히 나오는 순서를 정해준 형태

• 아래와 같이 queue 모듈의 PriorityQueue 클래스는 내부적으로 Heap 구조를 사용하여 복잡도는 O(logn)

구현은 아래와 같다.

# queue 에서 Priority Queue 호출
from queue import PriorityQueue
pq = PriorityQueue()

# 숫자를 임의로 집어넣어도 작은 순서대로 호출
pq.put(2)
pq.put(3)
pq.put(1)

# 호출시 가장 작은 값이 호출
pq.get()

 

특정 값을 순서대로 정렬하고 싶을때에는 튜플형식을 활용하여 사용할 수 있다.

# 특정 값의 순서를 맞춰주고 싶을 때 튜플형식으로 사용
from queue import PriorityQueue
pq = PriorityQueue()

# 중간에 넣은 a 가 먼저나오게 튜플 (1, a) 형식으로 입력
pq.put((2, 'b'))
pq.put((1, 'a'))
pq.put((3, 'c'))

# 가장 작은 값인 (1, a) 호출
pq.get()