힙이란?
힙(Heap)은 항상 최솟값(또는 최댓값)을 빠르게 꺼낼 수 있도록 유지되는 완전 이진 트리입니다. 우선순위 큐(priority queue)의 표준 구현으로, 다익스트라 최단경로·허프만 코딩·작업 스케줄링처럼 "다음으로 가장 급한 것"을 반복해서 꺼내야 할 때 쓰입니다.
핵심 한 줄: "전부 정렬하지 않고, 극값 하나만 O(log n)에 관리한다." 전체 정렬(O(n log n))이 필요 없을 때 힙이 훨씬 경제적입니다.
배열로 표현하는 완전 이진 트리
힙은 보통 배열 하나로 구현합니다. 인덱스 i에 대해
- •왼쪽 자식 =
2i + 1, 오른쪽 자식 =2i + 2, 부모 =(i - 1) / 2
최소 힙은 "부모 ≤ 두 자식"을 항상 만족합니다(최대 힙은 반대). 그래서 루트에 항상 최솟값이 있습니다. 단, 형제끼리의 순서는 보장되지 않습니다 — 힙은 "완전 정렬"이 아니라 "부모-자식 관계"만 지킵니다.
두 가지 핵심 연산
삽입(push): 새 값을 배열 맨 끝에 넣은 뒤, 부모보다 작으면 부모와 자리를 바꾸며 위로 올라갑니다(sift-up). 제자리를 찾으면 멈춥니다.
삭제(pop): 루트(최솟값)를 꺼내 반환하고, 맨 끝 원소를 루트로 옮긴 뒤, 더 작은 자식과 자리를 바꾸며 아래로 내려갑니다(sift-down).
두 연산 모두 트리 높이만큼만 이동하므로 O(log n)입니다.
동작 원리
1단계. push: 끝에 추가 → 부모와 비교 → 규칙 위반이면 교환(sift-up) → 루트까지 또는 멈출 때까지 반복.
2단계. peek: 루트(arr[0])를 보면 O(1)에 최솟값을 알 수 있습니다.
3단계. pop: 루트와 마지막을 교환하고 마지막을 제거 → 새 루트를 더 작은 자식과 비교 → 위반이면 교환(sift-down) → 리프까지 또는 멈출 때까지 반복.
알고노트 시각화는 sift-up과 sift-down에서 어떤 노드끼리 비교·교환되는지 색으로 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 연산 | 복잡도 |
|---|---|
| 삽입/삭제 | O(log n) |
| 최솟값 확인(peek) | O(1) |
| 힙 만들기(build) | O(n) |
| 공간 | O(n) |
예시로 따라가기
최소 힙에 5, 3, 8, 1을 차례로 넣어 봅시다.
- •5 삽입 → [5]
- •3 삽입 → 부모 5보다 작아 올라감 → [3, 5]
- •8 삽입 → 부모 3보다 큼, 그대로 → [3, 5, 8]
- •1 삽입 → 5보다 작아 올라가고, 다시 3보다 작아 올라감 → [1, 3, 8, 5]
이제 pop하면 최솟값 1이 먼저 나옵니다.
자주 하는 실수
- •완전 정렬로 착각: 힙 배열을 그대로 출력해도 정렬된 게 아닙니다(형제 순서 미보장).
- •최소/최대 혼동: 비교 부등호 방향 하나로 최소 힙↔최대 힙이 바뀝니다.
- •임의 원소 삭제: 위치를 모르면 탐색에 O(n)이 듭니다. 위치를 알면 그 자리에서 sift로 O(log n).
알고노트에서 직접 확인하세요
값이 삽입될 때 위로 올라가고(sift-up), 루트가 빠질 때 아래로 내려가는(sift-down) 과정을 알고노트에서 단계별로 확인할 수 있습니다.