언제 쓰나
- “매번 가장 작은/큰 것을 꺼내서 처리하라” — 시뮬레이션형 문제의 단골
- “K번째로 작은 수”, “상위 K개 유지”
- 다익스트라 최단 경로처럼 “지금까지 발견한 후보 중 최선부터” 확장하는 알고리즘
정렬과의 차이는 동적이라는 점이다. 값이 계속 추가되는 중에도 최솟값을 O(log n)에 꺼낼 수 있다. 한 번 정렬하고 끝나는 문제면 정렬로 충분하다.
핵심 아이디어
힙은 “부모가 자식보다 작다”는 규칙만 지키는 느슨한 이진 트리다. 전체가 정렬되어 있지는 않지만, 루트가 항상 최솟값인 것은 보장된다.
1 pop() → 1을 꺼내면
/ \ 마지막 원소를 루트로 올린 뒤
3 2 자식과 비교하며 가라앉힌다(sift down)
/ \ / → 트리 높이만큼만 이동: O(log n)
7 5 4
배열로 표현: [1, 3, 2, 7, 5, 4]
부모 i의 자식은 2i+1, 2i+2완전히 정렬하는 대신 “최솟값 하나”만 보장하기 때문에, 삽입도 삭제도 트리 높이인 O(log n)에 끝난다.
코드 템플릿
파이썬 heapq는 리스트를 최소 힙으로 다룬다.
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heap[0] # 최솟값 확인 → 1 (제거 안 함)
heapq.heappop(heap) # 최솟값 꺼내기 → 1
# 기존 리스트를 힙으로: O(n)
arr = [5, 3, 8, 1]
heapq.heapify(arr)최대 힙이 필요하면 부호를 뒤집어 넣고, 꺼낼 때 다시 뒤집는다.
heapq.heappush(heap, -x)
largest = -heapq.heappop(heap)우선순위와 데이터를 함께 다룰 때는 튜플을 넣는다. 튜플은 첫 원소부터 비교하므로 (우선순위, 값) 순서면 된다.
heapq.heappush(heap, (dist, node)) # 다익스트라의 기본 형태
d, node = heapq.heappop(heap)풀이 과정 따라가기
heappush(3) → heappush(1) → heappush(2) → heappop()에서 힙 리스트가 변하는 과정이다.
함정
heap[0]외의 원소는 정렬 상태가 아니다.heap[1]이 두 번째로 작은 값이라는 보장이 없다. 순서대로 필요하면 pop을 반복해야 한다.- 임의 원소 삭제는 지원하지 않는다. 다익스트라에서 거리가 갱신된 노드를 힙에서 지우는 대신, 꺼낼 때 “이미 처리된 노드면 건너뛰기”로 우회하는 것이 정석이다.
- 비교 불가능한 값. 우선순위가 같은 튜플이 있으면 다음 원소끼리 비교하는데, 비교 연산이 없는 객체가 그 자리에 오면 예외가 난다.
(우선순위, 일련번호, 객체)처럼 중간에 고유 번호를 끼워 해결한다.