[Python] 우선순위 큐

• 우선순위 큐는 원소들이 우선순위를 가진다.
• 힙(완전이진트리)으로 구현가능하다. 
• 삽입, 삭제, get 모두 O(logN)
• PriorityQueue 혹은Heapq으로 모듈 제공.
• Heapq이 빨라 많이 사용된다.
• 둘다 최소힙만 제공하므로 최대힙을 원하면 - 부호 활용하기.

import heapq

hq = []
heapq.heappush(heap, item) # 힙 형태를 유지하며 heap에 item push
heapq.heappop(heap) # 힙 형태를 유지하며 가장 작은 원소 pop. 비어있으면 IndexError

from queue import PriorityQueue

pq = PriorityQueue()

pq.put(1)

pq.get() # 1

 

 

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

이 문제에서 사용한 알고리즘. 그리디 + 우선순위큐