heap

✅ heapq란?

• heapq는 최소 힙(min-heap) 기반의 우선순위 큐 구현.
• 즉, 가장 작은 값이 가장 먼저 나옴.
• 정렬은 안 되어 있어도, 항상 heap[0]이 최소값.

⚙️ 주요 함수들

🔹 heapq.heappush(heap, item)

heap에 item을 힙 조건 유지하면서 삽입

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heap)  # [1, 3, 5]

🔹 heapq.heappop(heap)

heap에서 가장 작은 값을 꺼냄 (그리고 제거함)

x = heapq.heappop(heap)
print(x)     # 1 (가장 작은 값)
print(heap)  # [3, 5]

❓ 일반 pop()과 뭐가 다른데?

메서드	설명
list.pop()	기본적으로 맨 뒤의 요소를 꺼냄 (O(1))
heapq.heappop()	최소값을 꺼냄. 내부적으로 정렬 구조 유지 필요 (O(log n))

즉,

• pop()은 단순한 스택/큐
• heappop()은 항상 우선순위가 가장 높은 요소(최소값) 반환

🧠 힙의 구조 예시

heap = [1, 3, 5, 7, 9, 8]

이건 정렬된 게 아니라, "부모 노드는 자식보다 작다" 는 조건만 만족하는 구조 (min-heap).

🏁 요약

함수	설명
heappush(heap, item)	힙에 원소 삽입 (O(log n))
heappop(heap)	힙에서 최소값 제거 + 반환 (O(log n))
heap[0]	최소값 확인 (제거는 안 함, O(1))

---

😎 Max-Heap 만드는 방법 (Python에서는 기본 지원 안함)

Python에서는 heapq가 min-heap만 지원해서,
max-heap을 만들려면 값을 음수로 바꿔서 넣는 트릭을 써야 함!

✅ Max-Heap 예시

import heapq

nums = [3, 1, 5, 7, 2]
max_heap = []

# 값을 음수로 바꿔서 push
for num in nums:
    heapq.heappush(max_heap, -num)

# 가장 큰 값부터 pop (음수니까 다시 부호를 바꿔야 함)
while max_heap:
    print(-heapq.heappop(max_heap), end=' ')

🔽 출력 결과:

7 5 3 2 1

💡 핵심 아이디어

원래 값	넣을 때	꺼낼 때
7	-7	-(-7) → 7
5	-5	-(-5) → 5

📦 정리

종류	구현 방법	우선순위 기준	heapq 지원
Min-Heap	기본 heapq	작은 값이 먼저	✅ 기본
Max-Heap	-값으로 넣고 -로 꺼냄	큰 값이 먼저	❌ 직접 구현

✨ 추가: 튜플 우선순위 (정렬 기준 설정)

heapq.heappush(heap, (-priority, value))  # 우선순위 높은 게 먼저

이런 식으로 "우선순위 큐"의 우선 기준을 수동으로 조절할 수도 있음.