3. 모든 노드가 끝까지 내려가지는 않는다
해설글
작성 · 3분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
O(n log n)처럼 보였던 반복
힙 생성은 정렬되지 않은 배열을 부모 >= 자식인 최대 힙으로 바꾸는 작업이다. 2편처럼 빈 힙에 원소를 하나씩 넣고 매번 up-heap할 수도 있고, 배열을 완전이진트리로 본 뒤 내부 노드에 down-heap을 적용할 수도 있다.
리프는 자식이 없으므로 혼자서 이미 힙이다. 1번 인덱스 배열에서 원소가 n개라면 리프는 floor(n/2)+1..n, 마지막 내부 노드는 floor(n/2)다. 상향식 생성이 마지막 내부 노드부터 루트까지 거꾸로 처리하는 이유다.
[3, 9, 2, 7, 6]
3 배열을 트리로 해석
/ \
9 2
/ \
7 6
처음에는 루트 3이 자식 9보다 작아 최대 힙이 아니다. 아래 내부 노드부터 고치면 자식 서브트리가 먼저 힙이 되고, 부모를 내릴 때 어느 자식과 바꿀지 안전하게 결정할 수 있다.
| 처리할 인덱스 | 처리 전 | 처리 후 | 이유 |
|---|---|---|---|
| 2 | 3 9 2 7 6 |
3 9 2 7 6 |
9가 자식 7, 6보다 크므로 유지 |
| 1 | 3 9 2 7 6 |
9 7 2 3 6 |
3을 더 큰 자식 9와 바꾸고, 이어서 7과 바꿈 |
결과 배열은 오름차순이나 내림차순이 아니지만 모든 부모가 자식 이상이므로 최대 힙이다. 힙 생성은 정렬이 아니라 루트에서 최댓값을 빨리 꺼낼 수 있는 부분 순서를 만드는 일이다.
힙 노트에는 생성 방법이 둘로 나뉘어 있다. 원소를 하나씩 넣으며 UpHeap을 하는 삽입식과, 모든 원소를 배열에 놓은 뒤 부모들에 DownHeap을 하는 상향식이다. 노트에는 삽입식은 O(n log n), 상향식은 O(n)이라고 적혀 있다.
부모가 대략 n/2개이고 DownHeap 하나의 최악 시간이 O(log n)이라는 두 사실만 곱하면 O(n log n)이 나온다. 그러나 이 계산은 모든 부모가 루트처럼 바닥까지 내려갈 수 있다고 가정한다. 실제 힙에는 바닥에 가까운 부모가 훨씬 많다.
아래에서 위로 만드는 이유
저장소의 반복 구현은 마지막 부모 n/2부터 루트 1까지 거꾸로 올라간다.
void build_heap(void) {
for (int i = n / 2; i >= 1; --i) {
down_heap(i);
}
}
리프는 자식이 없어 이미 하나짜리 힙이다. 마지막 부모부터 DownHeap하면 그 자식들은 이미 힙이고, 그다음 부모를 처리할 때도 두 자식 서브트리는 이미 힙이다. 그래서 현재 부모 하나만 알맞은 경로로 내려보내면 서브트리 전체가 힙이 된다.
노트의 재귀 구현도 같은 순서를 다른 모양으로 표현한다. 왼쪽과 오른쪽 자식을 먼저 호출한 다음 현재 노드에 DownHeap을 적용한다. 실행 순서는 postorder다. 반복 구현과 재귀 구현의 핵심은 모두 “자식 힙을 먼저 완성한다”는 데 있다.
내려갈 수 있는 거리의 합
노트의 k번째 작은 수 과제에는 높이별 계산이 남아 있다. 리프 바로 위의 노드는 대략 n/4개이고 한 층 정도만 내려간다. 그 위 노드는 대략 n/8개이고 두 층, 다시 그 위는 n/16개이고 세 층 내려갈 수 있다.
따라서 전체 이동의 상한은 다음 모양이다.
(n/4)×1 + (n/8)×2 + (n/16)×3 + ...
노드 수는 위로 갈수록 절반으로 줄고, 내려갈 거리는 한 칸씩만 늘어난다. 1/2 + 2/4 + 3/8 + ... 형태의 합은 상수에 수렴하므로 전체는 n의 상수배, 즉 O(n)이다. DownHeap의 최악 비용을 모든 호출에 그대로 곱하면 트리의 위치 정보를 버리게 된다.
두 생성법을 작은 배열에서 확인
이번에 만든 재현 코드는 1..15 오름차순 입력을 삽입식과 상향식으로 각각 힙으로 만든다. 두 결과 배열의 모양은 같을 필요가 없다. 최대 힙은 부모가 자식 이상이라는 부분 순서만 요구하기 때문이다. 대신 두 결과 모두 모든 부모·자식 관계를 검사했다.
이 입력에서 재현 코드는 상향식 11회, 삽입식 34회의 swap을 기록했다. 이 숫자는 모든 n에서의 공식이나 일반 성능 결론이 아니라, 이번 고정 입력에서 실제로 센 결과다. 중요한 차이는 어디에서 작업이 시작되는가다. 삽입식은 새 원소가 매번 리프에서 위로 올라갈 수 있지만, 상향식에서는 많은 노드가 바닥 가까이에서 짧게만 움직인다.
시간 복잡도는 반복문 개수만 보고 정해지지 않는다. 각 반복이 어느 높이의 노드에서 시작하는지를 함께 세어야 한다. 모든 호출에 동일한 최악 비용을 적용하는 대신 “높이별 노드 수 × 가능한 이동 거리”를 합하면 상향식 힙 생성의 O(n)이 보인다.
참고한 기록과 코드
- 개인 노트 「3주차 - 힙, 힙순서 성질 유지」, 2025-10-20
- 개인 노트 「1001 알고리즘 과제」, 2025-10-01
Week3(Heap)/0915-2.cWeek3(Heap)/3-2.c