Priority Queue (우선 순위 큐)

기본적으로 Heap 구조로 구성되는데, 이 Heap 구조는 이진 트리(binary tree) 형태로 구현된다.

예를 들어 Priority Queue 안의 Heap 구조를 출력해보기 위해서는 다음과 같은 함수를 사용하면 된다.

from queue import PriorityQueue

priority_queue = PriorityQueue()

priority_queue.put(1)
priority_queue.put(5)
priority_queue.put(2)
priority_queue.put(10)
priority_queue.put(-99)
priority_queue.put(7)
priority_queue.put(5)

print(priority_queue.queue)

이를 출력 하면 다음과 같은 결과를 받아볼 수 있다.

[-99, 1, 2, 10, 5, 7, 5]

우선 순위큐는 우선 순위에 따라 정렬된 값을 뽑아낸다고 알고 있었는데, 출력 결과는 일부는 정렬된것 같기도 하지만, 부분 부분 정렬되지 않은 모습을 보인다. 왜 그럴까?

앞서 말했듯이 방금 호출한 priority_queue.queue 는 이 우선 순위큐에 들어온 Heap 구조. 즉 이진 트리를 리스트로 출력한 것이다.

우리가 원한 우선순위에 따라 출력되는 결과를 얻어내기 위해서는 get() 메서드를 이용해 하나씩 뽑아내야한다.

while priority_queue:
  print(priority_queue.get())

이렇게 출력하면 다음과 같은 결과를 받아볼 수 있다.

[-99, 1, 2, 5, 5, 7, 10]

우선 순위큐의 이진 트리에 값이 추가되는 순서를 그림으로 보면 다음과 같다.

그렇다면 어떤 방식으로 정렬되는걸까? 기본적으로 파이썬의 PriorityQueue는 최소힙 구조를 따른다. 이 말은 큐의 가장 앞에 있는 루트 노드의 값이 최소임을 의미한다.

큐는 FIFO 구조이기 때문에, get() 메서드를 호출하게되면 가장 앞에 있는 루트 노드의 값이 출력되는것이다.

이후에 빈 루트 노드를 채우기 위해서, 리스트 배열의 마지막 인덱스에 해당하는 노드를 루트 노드로 가져오고, 최소힙 규칙에 따라 새롭게 정렬한다.

이러한 과정을 반복하기 때문에, PriorityQueue를 직접 리스트로 출력했을 경우와 get()을 통해 하나씩 꺼내 출력했을 경우의 결과가 달라짐을 알 수 있다.

이를 그림으로 표현 하면 다음과 같다.

파이썬에서 제공하는 Priority Queue로는 다음과 같은 기능을 수행할 수 있다.

1. 요소를 추가할 때, 각 요소에 우선순위를 부여할 수 있습니다.
2. 우선순위가 높은 요소에 먼저 접근할 수 있습니다.
3. 요소를 추출할 때, 우선순위가 높은 요소를 먼저 추출합니다.
4. 요소를 추출하지 않고, 우선순위가 높은 요소를 확인할 수 있습니다.

이러한 특징 덕분에 다익스트라 알고리즘과 중간값 찾기 알고리즘에서 자주 사용된다.