홍라이프 계산기이진 힙 인덱스 계산기 쉽게 이해하기 — 개념과 원리
이진 힙은 보통 노드를 포인터로 연결하지 않고 일반 배열에 저장하며, 트리 구조는 위치로 표현합니다. 이 계산기는 0부터 시작하는 배열 인덱스를 넣으면 그 노드의 부모, 두 자식, 트리에서의 깊이를 알려 줍니다. 힙 정렬이나 우선순위 큐를 구현하거나 위로 올리기(sift-up), 아래로 내리기(sift-down) 코드를 점검할 때 유용합니다.
계산 방법
- 부모: ⌊(i − 1) ÷ 2⌋이며, 인덱스 0은 루트라 부모가 없습니다.
- 자식: 왼쪽 2i + 1, 오른쪽 2i + 2
- 깊이: ⌊log₂(i + 1)⌋이며, 루트의 깊이는 0입니다.
자식 인덱스가 힙 크기보다 작을 때만 실제로 존재하는 자식입니다.
원리
힙은 완전 이진 트리입니다. 마지막 층을 뺀 모든 층이 꽉 차 있고, 마지막 층은 왼쪽부터 채웁니다. 노드를 위층부터 왼쪽에서 오른쪽 순서로 읽으면 그대로 배열 순서가 됩니다. 깊이 d인 층에는 노드가 2ᵈ개 있고 인덱스 2ᵈ − 1에서 시작합니다. 앞선 노드들의 자식이 차례로 두 개씩 자리를 차지하므로 노드 i의 자식은 2i + 1과 2i + 2가 되고, 이를 거꾸로 풀면 부모 공식이 나옵니다. 포인터가 필요 없어 메모리를 아끼고 캐시 효율도 좋습니다. 교재에서 많이 쓰는 1부터 시작하는 인덱스라면 부모는 ⌊i ÷ 2⌋, 자식은 2i와 2i + 1입니다.
예제 풀이
- 입력값: i = 5입니다.
- 부모: ⌊(5 − 1) ÷ 2⌋ = 2입니다.
- 자식: 2 × 5 + 1 = 11, 2 × 5 + 2 = 12이므로 11, 12입니다.
- 깊이: ⌊log₂ 6⌋ = ⌊2.585⌋ = 2입니다.
확인해 보면 깊이 2인 층은 인덱스 3~6이고, 인덱스 2의 자식은 5와 6이므로 5는 왼쪽 자식입니다.
| 노드 인덱스 (0부터) | 부모 |
|---|---|
| 1.25 | 0 |
| 2.5 | 0 |
| 3.75 | 1 |
| 5 | 2 |
| 6.25 | 2 |
| 7.5 | 3 |
| 10 | 4 |
결과 해석
깊이는 이 노드에서 위로 올리기를 할 때 최대 몇 번 교환하는지를 알려 줍니다. 원소가 n개인 힙의 높이는 ⌊log₂ n⌋이므로 삽입과 최솟값(최댓값) 꺼내기는 O(log n)입니다. 크기가 12인 힙이라면 인덱스 12가 범위를 벗어나므로 인덱스 5는 왼쪽 자식(11)만 가집니다. 잎이 아닌 마지막 노드는 ⌊n ÷ 2⌋ − 1이며, 상향식 힙 구성은 여기서 시작합니다.
흔한 실수
- 0부터 시작하는 공식과 1부터 시작하는 공식을 섞어 쓰면 오류 없이 힙이 깨집니다.
- 자식 인덱스가 힙 크기보다 작은지 확인하지 않습니다.
- 0 쪽으로 버리는 정수 나눗셈 언어에서 i = 0에 (i − 1) / 2를 계산하면 0이 나오므로 먼저 i > 0인지 확인해야 합니다.
자주 묻는 질문
힙은 정렬된 배열인가요?
아닙니다. 부모가 자식보다 작거나(최소 힙) 크다는(최대 힙) 것만 보장하며 형제끼리는 순서가 없습니다.
원소 n개로 힙을 만드는 데 얼마나 걸리나요?
상향식으로 만들면 O(n)이며, 하나씩 삽입하는 O(n log n)보다 빠릅니다.
우선순위 큐에 왜 힙을 쓰나요?
최솟값이나 최댓값을 O(1)에 확인하고, 삽입과 삭제를 추가 메모리 없이 O(log n)에 처리하기 때문입니다.
출처: J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM 7(6), 1964 · T. H. Cormen 외, Introduction to Algorithms, MIT Press