응급실 대기실을 떠올려 보세요. 온 순서대로 부르지 않고 가장 급한 환자부터 부릅니다. 그렇다고 대기 중인 사람 전부를 위중한 순서로 완벽히 줄 세워 두지는 않습니다 — 새 환자가 올 때마다 전부 다시 줄 세우면 접수대가 마비될 테니까요. 필요한 것은 딱 하나, "다음에 부를 사람이 누구인가"가 언제나 맨 앞에 있다는 보장뿐입니다.
힙은 전체를 정렬하지 않고 "가장 작은 것(또는 가장 큰 것) 하나"만 항상 맨 앞에 유지하는 자료구조입니다.
완전 정렬: 전부 줄 세움 — 새 원소가 들어올 때마다 비쌈
힙: 맨 앞만 보장 — 넣기도 꺼내기도 싸고, 꺼내는 값은 항상 최솟값
빈 최소 힙에 5, 3, 8을 차례로 넣고 하나를 꺼내 봅니다. 힙은 배열 하나로 표현하며, 규칙은 "부모가 자식보다 작거나 같다" 하나뿐입니다.
단계
하는 일
배열 상태
무슨 일이
시작
—
[]
빈 힙
1
5 넣기
[5]
끝에 붙임
2
3 넣기
[5, 3] → [3, 5]
부모 5 > 자식 3이라 자리를 맞바꿈
3
8 넣기
[3, 5, 8]
부모 3 ≤ 8이라 그대로
4
꺼내기
[3, 5, 8] → 반환값 3
맨 앞 3을 꺼냄
5
빈자리 메우기
[8, 5] → [5, 8]
마지막 8을 맨 앞에 올린 뒤 작은 자식과 맞바꿈
[3, 5, 8]은 정렬된 것처럼 보이지만 힙은 정렬을 보장하지 않습니다. 보장하는 것은 맨 앞이 최솟값이라는 사실 하나이고, 그 대가로 넣기·꺼내기가 자리 교환 몇 번(트리 높이만큼, 즉 O(log N))으로 끝납니다.
힙은 트리처럼 생각하고 배열로 구현합니다. 인덱스 규칙만 알면 됩니다.
위치
인덱스
i의 부모
(i - 1) >> 1
i의 왼쪽 자식
2 * i + 1
i의 오른쪽 자식
2 * i + 2
값은 배열 하나에 담습니다. 트리 구조를 따로 만들 필요가 없습니다.
class MinHeap { private a: number[] = []; get size() { return this.a.length; }}
넣을 때는 끝에 붙인 뒤 위로 올립니다(bubble-up). 부모보다 작으면 부모와 자리를 바꾸고, 그 자리에서 다시 확인합니다.
a.push(v);let i = a.length - 1;while (i > 0 && a[(i - 1) >> 1] > a[i]) { const p = (i - 1) >> 1; [a[p], a[i]] = [a[i], a[p]]; i = p;}
꺼낼 때는 맨 앞을 빼고, 마지막 원소를 그 빈자리에 올립니다. 힙에 원소가 하나뿐인 경계를 잊지 않도록 조심합니다.
const top = a[0];const last = a.pop()!;if (a.length > 0) a[0] = last;
올려놓은 원소를 아래로 내립니다(bubble-down). 반드시 두 자식 중 더 작은 쪽과 비교해서 내려갑니다.
const l = 2 * i + 1, r = 2 * i + 2;let m = i;if (l < a.length && a[l] < a[m]) m = l;if (r < a.length && a[r] < a[m]) m = r;
전체 코드 — TS에는 내장 힙이 없어서 직접 구현해야 합니다. 한국 코테에서 TS/JS를 쓸 때의 유일한 진입 장벽이며, 아래 20여 줄은 외워서 칠 수 있어야 합니다.
class MinHeap { private a: number[] = []; get size() { return this.a.length; } push(v: number): void { const a = this.a; a.push(v); let i = a.length - 1; while (i > 0) { // 2단계: bubble-up const p = (i - 1) >> 1; if (a[p] <= a[i]) break; [a[p], a[i]] = [a[i], a[p]]; i = p; } } pop(): number { const a = this.a; const top = a[0]; // 3단계: 맨 앞을 빼고 마지막을 올림 const last = a.pop()!; if (a.length > 0) { a[0] = last; let i = 0; for (;;) { // 4단계: bubble-down const l = 2 * i + 1, r = 2 * i + 2; let m = i; if (l < a.length && a[l] < a[m]) m = l; if (r < a.length && a[r] < a[m]) m = r; if (m === i) break; [a[m], a[i]] = [a[i], a[m]]; i = m; } } return top; }}
"가장 작은/큰 것을 반복해서 꺼내며 갱신" — 두 재료를 합쳐 다시 넣는 류
K번째 최소/최대 유지 — 크기 K 힙
작업 스케줄링 — "지금 가능한 것 중 우선순위가 가장 높은 것" (그리디 + 힙)
다익스트라 최단 경로의 핵심 부품
정렬(O(N log N))로도 되지만, 중간에 원소가 계속 추가·제거되면 매번 재정렬은 O(N² log N) — 그때가 힙의 자리입니다.
// 반복 병합 — 가장 작은 둘을 꺼내 합쳐 다시 넣기const h = new MinHeap();for (const v of items) h.push(v);let cost = 0;while (h.size >= 2) { const merged = h.pop() + h.pop(); cost += merged; h.push(merged);}
// 최대 힙 — 부호를 뒤집어 최소 힙에 담고, 꺼낼 때 되돌림const h = new MinHeap();for (const v of items) h.push(-v);const max = -h.pop();
// K개 유지 — 크기 K를 넘으면 가장 작은 것을 버림 → 남는 것이 상위 K개const h = new MinHeap();for (const v of items) { h.push(v); if (h.size > k) h.pop();}// 이때 h의 맨 앞이 곧 K번째로 큰 값
객체를 담으려면 비교 부분을 cmp(a[p], a[i]) <= 0 형태로 바꾸고, 비교 함수를 생성자로 받게 하면 됩니다.
pop에서 마지막 원소를 루트로 올리는 처리를 빠뜨림 (힙이 1개일 때 경계)
const top = a[0]; a[0] = a.pop()!; // 원소 1개면 a[0]에 undefined가 남음const top2 = a[0]; const last = a.pop()!;if (a.length > 0) a[0] = last; // 빈 힙이 되는 경우를 분리
bubble-down에서 두 자식 중 작은 쪽 과 비교하지 않고 왼쪽만 봄
if (l < a.length && a[l] < a[i]) m = l; // 오른쪽 자식이 더 작으면 규칙 깨짐if (l < a.length && a[l] < a[m]) m = l;if (r < a.length && a[r] < a[m]) m = r; // 둘 다 보고 더 작은 쪽
a.sort()를 매 턴 호출하는 "가짜 힙" — 작은 입력은 통과하지만 큰 케이스에서 시간 초과
부모 인덱스 (i - 1) >> 1을 i >> 1로 잘못 씀 (0-기반 배열 기준을 헷갈림)
왜 배열 하나로 트리가 되는가: 힙은 "부모 ≤ 자식" 규칙만 지키는 완전 이진 트리 입니다. 완전 이진 트리는 빈칸 없이 위에서 아래로, 왼쪽에서 오른쪽으로 채워지므로 노드에 번호를 매기면 부모·자식 관계가 곱셈과 덧셈으로 계산됩니다. 포인터를 저장할 필요가 없어 메모리도 아낍니다.
왜 O(log N)인가: bubble-up과 bubble-down은 트리의 한 층씩만 이동합니다. 완전 이진 트리의 높이는 노드가 N개일 때 약 log₂N이므로 최악에도 그만큼만 교환합니다. 반면 루트가 항상 최솟값이라는 것 외에는 아무 순서도 보장하지 않기 때문에, 전체를 정렬해야 하는 작업에 힙 하나로 답하려 하면 결국 N번 꺼내야 해서 O(N log N)이 됩니다.
최대 힙 만들기: 비교 부호만 뒤집거나, 값에 -1을 곱해 넣습니다. 부호를 뒤집는 방식은 값이 실수·큰 정수일 때도 안전하지만, 꺼낸 뒤 되돌리는 것을 잊기 쉬우므로 비교 함수를 바꾸는 편을 권합니다.
시각화로 bubble-up/down의 움직임을 본 뒤, 힙 기본 조작 → 반복 병합 → 스케줄링(그리디 결합) 순으로 푸세요. MinHeap 클래스를 보지 않고 3번 쳐 보는 것이 최고의 연습입니다.