[Algorithm] 우선순위 큐

* Python을 기준으로 합니다

---

우선순위 큐 (Priority Queue)

- 개념

• 우선순위 큐 : 우선순위가 높은 데이터를 가장 먼저 삭제하는 큐
  • 즉, 우선순위 큐는 데이터를 우선순위에 맞게 정렬하고 순서대로 추출할 수 있어야 함
  • 이때 배열이나 연결 리스트를 사용한 구현은, 우선순위에 따른 삽입과 삭제에 많은 비용이 소모됨
  • 따라서 우선순위 큐는 힙 자료구조를 사용하여 삽입과 삭제를 $O(\log n)$ 내에 처리하도록 함
    1. 우선순위 큐에서 최소힙을 적용하면 값이 작을수록 높은 우선순위를 부여하도록 할 수 있음
    2. 반대로 최대힙을 적용하면 값이 클수록 우선순위를 부여함
       - 힙은 일반적으로 최소힙으로 구현되므로, 삽입 시 음수를 취하고 추출 시 다시 -1을 곱하는 방식으로 처리

우선순위 큐

- 구현

1. heapq 라이브러리를 이용한 우선순위 큐의 구현

• 우선순위 큐는 힙 자료구조에 기반하므로, 힙과 마찬가지로 `heapq` 라이브러리를 사용해 구현함
  • `heapify(list)` : 주어진 배열을 우선순위 큐로 생성
  • `heappush(heap, data)` : 우선순위 큐에 데이터 삽입
  • `heappop(heap)` : 우선순위 큐에서 최소값 추출

import heapq

prique = []

#우선순위 큐 삽입
heapq.heappush(prique, 90)
heapq.heappush(prique, 47)
heapq.heappush(prique, 13)
heapq.heappush(prique, 5)
heapq.heappush(prique, 84)

print(prique) #[5, 13, 47, 90, 84]

#우선순위 큐에서 우선순위에 따라 값 추출 (최소힙 기준 - 작을수록 높은 우선순위)
while prique:
  print(heapq.heappop(prique), end=' ') #5 13 47 84 90

• 우선순위를 지정하여 삽입하는 경우, `(우선순위(int), data)` 형식으로 push 함
  - 이때 우선순위 값이 작을수록 순위가 높음

import heapq

prique = []

#우선순위를 지정하여 삽입
heapq.heappush(prique, (5, 'E'))
heapq.heappush(prique, (1, 'A'))
heapq.heappush(prique, (4, 'D'))
heapq.heappush(prique, (2, 'B'))
heapq.heappush(prique, (3, 'C'))

print(prique) #[(1, 'A'), (2, 'B'), (4, 'D'), (5, 'E'), (3, 'C')]

#우선순위 큐에서 데이터 추출
while prique:
  print(heapq.heappop(prique)[1], end=' ') #A B C D E

2. queue 라이브러리를 이용한 우선순위 큐의 구현

• `queue` 라이브러리는 `PriorirtyQueue`라는 우선순위 큐 클래스를 제공함
  • BUT, 해당 라이브러리는 멀티 스레딩을 지원하는 것이 목적이므로 `heapq`를 사용하는 것이 더 효율적임
  • `put()` : 우선순위 큐에 데이터 삽입
  • `get()` : 우선순위 큐에서 데이터 추출
    

import queue

prique = queue.PriorityQueue()

#우선순위 큐 삽입
prique.put(90)
prique.put(47)
prique.put(13)
prique.put(5)
prique.put(84)

#우선순위 큐 추출
for i in range(5):
  print(prique.get(), end=' ') #5 13 47 84 90