heapq로 우선순위 큐 구현

heapq는 파이썬 표준 라이브러리에서 제공하는 최소 힙(min-heap) 구현 모듈이야.

우선순위 큐(priority queue)를 구현할 때 자주 쓰이고,

A* 알고리즘, 다익스트라 알고리즘 등에서도 핵심적으로 사용돼.

지금부터 heapq의 기본 사용법, 주요 함수, 예제까지 전부 정리해줄게.

✅ heapq의 핵심 개념

heapq는 **리스트(list)**를 heap 자료구조처럼 다룰 수 있게 해주는 모듈
파이썬의 기본 heapq는 최소 힙(min-heap) 기준

→ 즉, 항상 **가장 작은 값이 루트(맨 앞)**에 있음

✅ 주요 함수 요약

함수	설명	예시
`heapq.heapify(lst)`	리스트를 힙 구조로 바꿈	`heapify(lst)`
`heapq.heappush(heap, item)`	힙에 `item` 추가	`heappush(h, 5)`
`heapq.heappop(heap)`	가장 작은 값 제거 및 반환	`heappop(h)`
`heapq.heappushpop(heap, item)`	push 후 pop (더 효율적)
`heapq.heapreplace(heap, item)`	pop 후 push (항상 교체)

✅ 기본 예제

import heapq

nums = [4, 1, 7, 3, 8, 5]
heapq.heapify(nums)  # 리스트를 힙 구조로 변경
print(nums)          # 내부적으로 heap 구조로 재배열됨

heapq.heappush(nums, 2)  # 값 2 추가
print(heapq.heappop(nums))  # 가장 작은 값(1) 제거

print(nums)  # 현재 힙 상태

✅ 튜플을 이용한 우선순위 큐

힙은 값 자체의 대소로 우선순위를 판단하므로,

(우선순위, 데이터) 형태의 튜플로 넣는 게 일반적

import heapq

queue = []
heapq.heappush(queue, (2, "task B"))
heapq.heappush(queue, (1, "task A"))
heapq.heappush(queue, (3, "task C"))

print(heapq.heappop(queue))  # (1, 'task A')

→ 우선순위가 낮은 숫자가 먼저 pop됨 (min-heap)