요약
- 힙은 완전 이진 트리 + **힙 속성(부모가 자식보다 항상 큼/작음)**을 만족하는 자료구조다.
- 완전 이진 트리라 빈틈이 없어 포인터 없이 배열 하나로 표현되고, 인덱스 산술로 부모-자식을 오간다.
- peek는 O(1), insert/extract는 O(log n), 배열을 한 번에 힙으로 만드는 heapify는 O(n).
본문
힙 속성과 구조
- 최대 힙: 부모 ≥ 자식. 최소 힙: 부모 ≤ 자식.
- 힙 속성은 부모-자식 관계만 보장한다. 형제 노드 간 순서나 좌우 자식 간 순서는 보장하지 않으므로 힙은 정렬된 구조가 아니다.
- 힙은 항상 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 꽉 차고, 마지막 레벨은 왼쪽부터 빈틈없이 채워진다. 이 "빈틈 없음" 덕분에 배열에 인덱스 순서대로 담을 수 있다.
배열 표현 (인덱스 산술, 0-based)
완전 이진 트리를 위→아래, 왼→오 순서로 배열에 담으면:
| 관계 | 인덱스 |
|---|---|
| 왼쪽 자식 | 2i + 1 |
| 오른쪽 자식 | 2i + 2 |
| 부모 | (i - 1) / 2 (내림) |
자식 존재 여부는 인덱스가 배열 크기를 넘는지로 판단한다(범위 밖 = 잎 노드).
(1-based로 구현하면 왼쪽 2i, 오른쪽 2i+1, 부모 i/2로 더 깔끔해진다.)
핵심 연산 — 깨뜨렸다가 복구하기
| 연산 | 시작 위치 | 이동 방향 | 비교 대상 | 복잡도 |
|---|---|---|---|---|
| insert | 맨 끝에 추가 | 위로 (sift-up) | 부모 1명 | O(log n) |
| extract | 맨 끝을 루트로 이동 | 아래로 (sift-down) | 자식 2명 중 큰 쪽 | O(log n) |
| peek | 루트 조회만 | — | — | O(1) |
- insert: 완전 이진 트리 유지를 위해 맨 끝에 넣고, 부모보다 크면 swap하며 위로 올린다.
- extract: 흔한 함정 — "더 큰 자식을 끌어올린다"고 하면 완전 이진 트리 형태가 깨진다(구멍이 엉뚱한 위치에 생김). 표준은 맨 끝 원소를 루트로 옮기고 sift-down. 빠진 자리가 항상 맨 끝이라 형태가 안전하다.
- extract에서 자식 2명 중 더 큰 쪽과 교환해야 한다. 작은 쪽과 바꾸면 그 작은 값이 부모가 돼 힙이 또 깨진다.
- "루트 값을 빼는 것 자체"는 쉽지만 빼고 나서 힙을 복구하는 비용(sift-down, 높이만큼)이 있어 extract는 O(1)이 아니라 O(log n)이다.
heapify가 O(n)인 이유
- 아무 배열 → 힙: 마지막 부모 노드(
n//2 - 1)부터 루트(0)까지 거꾸로 sift-down. 잎 노드는 자식이 없어 순회에 포함조차 안 한다. - "잎을 스킵해서 O(n)"은 절반만 맞다. 잎을 빼도 남은 n/2개가 각각 log n이면 여전히 O(n log n)이다.
- 진짜 이유: sift-down 비용은 그 노드부터 바닥까지의 높이다. 잎 바로 위(n/4개)는 최대 1칸, 그 위(n/8개)는 최대 2칸... 루트(1개)만 log n칸. "개수 많은 노드는 거의 안 움직이고, 많이 움직이는 노드는 몇 개 없어서" 가중합이 O(n)으로 수렴한다.
0·(n/2) + 1·(n/4) + 2·(n/8) + 3·(n/16) + ... → O(n)
- 반대로 하나씩 n번 삽입은 sift-up이라 비용 구조가 뒤집힌다. 잎에서 루트로 올라가니 개수 많은 아래쪽 노드가 가장 비싸져 O(n log n)이 된다. 방향(아래로 vs 위로)이 비용을 뒤집는다.
완전 vs 균형 이진 트리 (헷갈림 주의)
- 완전(Complete): 차곡차곡 순서대로 채움(왼쪽부터). → 힙이 이것, 배열 표현의 전제.
- 균형(Balanced): 모든 노드에서 좌우 서브트리 높이차 ≤ 1. → AVL, 레드블랙 트리.
- 포함 관계: 완전 ⊂ 균형 (완전 트리는 항상 균형이지만, 균형이라고 완전은 아니다). 예) 2는 왼쪽 자식만, 3은 오른쪽 자식만 가지면 균형이어도 "왼쪽부터 채움" 위반이라 완전이 아니다.
사용처
peek O(1)이 강점이라 항상 최댓값/최솟값을 빠르게 꺼내야 하는 곳에 쓴다.
- 우선순위 큐의 표준 구현 (FIFO가 아니라 우선순위 순으로 꺼냄)
- 다익스트라 최단 경로, A* 길찾기 (가장 가까운/유망한 후보 먼저)
- Top-K 문제 (크기 K짜리 힙 유지), 작업 스케줄러
- 힙 정렬 (다 넣고 하나씩 꺼내면 정렬됨, in-place 가능)
파이썬 구현
def sift_down(heap, i, n):
while True:
largest, left, right = i, 2*i + 1, 2*i + 2
if left < n and heap[left] > heap[largest]:
largest = left
if right < n and heap[right] > heap[largest]:
largest = right
if largest == i: # 자식이 다 작으면 끝
break
heap[i], heap[largest] = heap[largest], heap[i]
i = largest
def build_heap(arr): # O(n)
n = len(arr)
for i in range(n // 2 - 1, -1, -1): # 마지막 부모 → 루트 (잎 제외)
sift_down(arr, i, n)
return arr
def push(heap, value): # sift-up, O(log n)
heap.append(value)
i = len(heap) - 1
while i > 0:
parent = (i - 1) // 2
if heap[i] > heap[parent]:
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
else:
break
def pop(heap): # 루트 꺼내기, O(log n)
if not heap:
return None
root = heap[0]
last = heap.pop()
if heap:
heap[0] = last
sift_down(heap, 0, len(heap))
return root
- 실무에선 표준 라이브러리
heapq를 쓴다. 단heapq는 최소 힙만 지원하므로, 최대 힙이 필요하면 값에-를 붙여 넣는다(heapq.heappush(h, -x)).