테마
힙과 우선순위 큐
힙(heap)은 부모가 자식보다 항상 크거나(최대 힙, max heap) 항상 작은(최소 힙, min heap) 완전 이진 트리(complete binary tree)다. 이 순서 규칙 덕분에 최댓값이나 최솟값이 늘 맨 위에 있어, 빅오 표기법(Big-O notation)으로 원소 수와 상관없는 O(1)에 확인한다. 모양이 완전 이진 트리라서 넣기와 꺼내기는 원소 수의 로그에 비례하는 O(log n)에 한다. "우선순위가 가장 높은 것부터 꺼내는" 우선순위 큐(priority queue)를 만드는 대표 자료구조(data structure)이며, 메모리 영역을 뜻하는 힙과는 이름만 같다.
힙 속성: 부모와 자식 사이의 규칙
힙은 두 조건을 동시에 지킨다.
- 모양: 완전 이진 트리다. 마지막 층을 뺀 모든 층이 꽉 차 있고, 마지막 층은 왼쪽부터 채운다.
- 순서: 최대 힙은 모든 부모가 자식보다 크거나 같고, 최소 힙은 모든 부모가 자식보다 작거나 같다.
순서 규칙은 부모와 자식 사이에만 있다. 형제끼리나 서로 다른 서브트리(subtree)끼리는 아무 순서가 없다. 그래서 힙은 정렬된 구조가 아니다. 예를 들어 배열(array) [1, 3, 2, 7, 4]는 올바른 최소 힙이지만 정렬돼 있지 않다. 힙이 보장하는 것은 "맨 위가 가장 작다(또는 크다)"뿐이다.
배열 표현
완전 이진 트리는 빈칸이 없으므로, 노드(node)를 위층부터, 같은 층에서는 왼쪽에서 오른쪽 순서로 배열에 차례로 담을 수 있다. 부모·자식 위치를 인덱스 계산으로 알 수 있어 포인터(pointer)가 필요 없다. 그래서 노드마다 주소를 따로 저장하지 않아 메모리를 아끼고, 원소가 메모리에 붙어 있어 접근도 빠르다. 이 문서는 Java PriorityQueue·Python heapq와 같은 0부터 세는 인덱스를 쓴다.
- i번 노드의 왼쪽 자식: 2i + 1
- i번 노드의 오른쪽 자식: 2i + 2
- i번 노드의 부모: (i − 1) / 2 (나머지는 버린다)
1부터 세는 교재에서는 왼쪽 자식 2i, 오른쪽 자식 2i + 1, 부모 i / 2가 된다. 어느 기준인지 먼저 확인해야 공식을 헷갈리지 않는다.
다이어그램 로딩…
넣기: 위로 올리기
새 값은 모양 규칙을 지키려고 먼저 맨 끝, 즉 배열의 마지막 칸에 넣는다. 그다음 부모와 비교해 순서 규칙을 어기면(최소 힙에서 부모보다 작으면) 부모와 자리를 바꾼다. 규칙이 맞을 때까지, 또는 루트 노드(root node)에 닿을 때까지 반복한다. 이를 위로 올리기(sift up)라 한다. 완전 이진 트리는 층이 하나 늘 때마다 담을 수 있는 노드 수가 두 배가 되므로, 원소가 n개면 높이는 약 log₂ n이다. 한 번 바꿀 때마다 한 층 올라가므로 O(log n)이다.
예를 들어 최소 힙 [1, 3, 2, 7, 4]에 0을 넣으면 다음처럼 올라간다.
| 단계 | 배열 | 0의 위치 | 비교 |
|---|---|---|---|
| 맨 끝에 넣기 | [1, 3, 2, 7, 4, 0] | 5 | 부모(위치 2) 값 2보다 작다 → 바꾼다 |
| 한 층 올라감 | [1, 3, 0, 7, 4, 2] | 2 | 부모(위치 0) 값 1보다 작다 → 바꾼다 |
| 루트 도착 | [0, 3, 1, 7, 4, 2] | 0 | 루트라서 멈춘다 |
java
void offer(int x) { // 최소 힙, a는 배열, size는 원소 수
int i = size++;
a[i] = x;
while (i > 0 && a[(i - 1) / 2] > a[i]) {
int p = (i - 1) / 2;
int t = a[p]; a[p] = a[i]; a[i] = t;
i = p;
}
}꺼내기: 아래로 내리기
꺼내는 값은 항상 루트 노드다. 루트를 빼면 빈자리가 생기므로, 배열의 마지막 원소를 루트 자리로 옮겨 모양을 맞춘다. 그다음 두 자식 중 더 작은 쪽(최소 힙 기준)과 비교해 자기가 더 크면 자리를 바꾸고 한 층 내려간다. 이를 아래로 내리기(sift down)라 하고, 역시 O(log n)이다. 두 자식 중 작은 쪽과 바꾸는 이유는, 큰 쪽을 올리면 그 값이 다른 자식보다 커서 순서 규칙이 깨지기 때문이다.
이어지는 내용은 힙과 우선순위 큐 2에서 다룬다.
면접 포인트
- "힙이 뭔가요?" → 부모-자식 순서 규칙을 지키는 완전 이진 트리. 루트가 최댓값(최대 힙)이나 최솟값(최소 힙).
- "힙은 정렬돼 있나요?" → 아니다. 부모-자식 사이 순서만 보장. 형제·다른 서브트리 사이엔 순서 없음.
- "넣기·꺼내기 복잡도는?" → O(log n)(위로 올리기·아래로 내리기), 맨 위 확인 O(1).
- "배열 인덱스 공식은?" → 0부터: 자식 2i+1·2i+2, 부모 (i−1)/2.