우선순위큐 (heapq)

✅ 우선순위 큐

heapq와 priorityqueue로 구현할 수 있는데,
코딩테스트에서는 시간이 빠른 heapq로 구현

heapq는 최소힙을 구성한다.

그래서 우선순위가 가장 낮은 애들(작은수)이 먼저 pop된다

📍 heapq에서는 . 앞에 다 heapq가 들어온다

💙 heapq 모듈 호출

import heapq

💙 리스트를 heapq로 바꾸기

heapq.heapify(list)

💙 heapq에 원소 삽입, 삭제

heapq.heappush(heap,x) # 삽입 / heappush 아님!
heapq.heappop(heap) # 삭제 / 값도 삭제되고 값도 리턴됨
heap[0] # 삭제말고 그냥 보고 싶을 때

💙 최대힙으로 구성하기

heapq.heappush(max_heap, (-item, item))


heap = [1,3,5,7,9]
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))
  #(-9,9), (-7,7) ...
max_item = heapq.heappop(max_heap)[1] # 두번째 값이 진짜니까
# 두번째값만 pop을 했지만 전체가 pop되는 것을 알 수 있다