[자료구조] 우선순위 큐의 파이썬 구현

  현재 상황에서 최선의 선택을 반복한다는 그리디 알고리즘의 특징 때문에 우선순위 큐는 특히 그리디 알고리즘에서 자주 사용된다. 파이썬에서 우선순위 큐를 구현할 수 있는 방법에는 두 가지가 있다.

우선순위 큐 : 값이 들어올 때마다 오름차순으로 정렬 & 값을 꺼내면 가장 작은 값부터 꺼내짐

💡 파이썬 모듈

(1) PriorityQueue

from queue import PriorityQueue

myque = PriorityQueue()

# 데이터 추가
myque.put(data)
# 데이터 추출
myque.get()
# 사이즈 반환
myque.qsize()
# 비었는지 확인
myque.empty()

(2) heapq

import heapq

myqueue = []

# 데이터 추가
heapq.heappush(myqueue, data)
# 데이터 추출
heapq.heappop(myqueue)
# 리스트 >> 힙 변환
heapq.heapify(myqueue)

💡 활용 예시 : 내림차순 정렬

 우선순위큐는 오름차순으로만 정렬되기 때문에 내림차순으로 정렬하기 위해서는 모든 값들에 -1을 곱해 값을 넣어주면 된다. 그리고 꺼낼때에도 동일하게 -1을 곱해 빼주면 원래의 값으로 돌려놓을 수 있다. 아래처럼 !

heapq.heappush(queue, -1 * data)
data = heapq.heappop(queue) * (-1)