힙 삽입·삭제 과정 계산기
숫자 목록으로 이진 힙을 만드는 두 가지 방법(하나씩 삽입 vs 상향식 heapify)을 나란히 돌려 비교·교환 횟수를 세고, 배열과 트리가 어떻게 대응하는지, 루트를 반복해 뽑으면 어떻게 정렬되는지 보여 줍니다.
공백이나 쉼표로 나눠 넣습니다. 63개까지 다룹니다.
비교 횟수 — 하나씩 삽입 vs 상향식
17회 vs 14회
같은 10개를 힙으로 만드는데 상향식이 3회 덜 비교했습니다. 삽입은 O(n log n), 상향식은 O(n)입니다.
① 하나씩 삽입 — 맨 뒤에 놓고 부모와 견주며 올린다
| 단계 | 올라간 자리 | 비교 | 교환 |
|---|---|---|---|
| 4 삽입 | [0] | 0 | 0 |
| 1 삽입 | [1] | 1 | 0 |
| 3 삽입 | [2] | 1 | 0 |
| 2 삽입 | [3] → [1] | 2 | 1 |
| 16 삽입 | [4] → [1] → [0] | 2 | 2 |
| 9 삽입 | [5] → [2] | 2 | 1 |
| 10 삽입 | [6] → [2] | 2 | 1 |
| 14 삽입 | [7] → [3] → [1] | 3 | 2 |
| 8 삽입 | [8] → [3] | 2 | 1 |
| 7 삽입 | [9] → [4] | 2 | 1 |
| 합계 | 17 | 9 | |
② 상향식 heapify — 마지막 내부노드부터 거꾸로 내린다
| 단계 | 내려간 자리 | 비교 | 교환 |
|---|---|---|---|
| i=4 내리기 (16) | [4] | 1 | 0 |
| i=3 내리기 (2) | [3] → [7] | 2 | 1 |
| i=2 내리기 (3) | [2] → [6] | 2 | 1 |
| i=1 내리기 (1) | [1] → [4] → [9] | 3 | 2 |
| i=0 내리기 (4) | [0] → [1] → [3] → [8] | 6 | 3 |
| 합계 | 14 | 7 | |
상향식이 싼 이유는 «내려갈 길이 짧은 노드가 많아서»입니다. 잎은 절반이나 되지만 아예 손대지 않고, 깊이 h인 노드는 많아야 n/2h+1개뿐인데 그중 내려갈 길은 h입니다. Σ h·n/2h+1이 2n으로 수렴해 전체가 O(n)이 됩니다.
완성된 힙 (상향식 결과)
| i | 값 | 부모 ⌊(i−1)/2⌋ | 왼자식 2i+1 | 오른자식 2i+2 |
|---|---|---|---|---|
| 0 | 16 | — | [1] 14 | [2] 10 |
| 1 | 14 | [0] 16 | [3] 8 | [4] 7 |
| 2 | 10 | [0] 16 | [5] 9 | [6] 3 |
| 3 | 8 | [1] 14 | [7] 2 | [8] 4 |
| 4 | 7 | [1] 14 | [9] 1 | — |
| 5 | 9 | [2] 10 | — | — |
| 6 | 3 | [2] 10 | — | — |
| 7 | 2 | [3] 8 | — | — |
| 8 | 4 | [3] 8 | — | — |
| 9 | 1 | [4] 7 | — | — |
힙에는 포인터가 없습니다. 배열 하나에 층 순서(위에서 아래로, 왼쪽에서 오른쪽으로)대로 담아 두고 인덱스 계산만으로 부모와 자식을 찾습니다. 그래서 완전 이진트리여야 하고, 중간에 빈자리가 생기면 이 대응이 깨집니다.
③ 힙 정렬 — 루트를 뽑아 뒤에 쌓는다
루트를 맨 뒤 자리와 바꾸고 힙 크기를 하나 줄인 뒤 다시 내립니다. 뽑힌 값이 뒤에서부터 쌓이므로 최대 힙이면 오름차순으로 정렬됩니다. 아래 표에서 진하게 칠한 뒤쪽이 이미 확정된 구간입니다.
1회차 — 16 확정, 남은 힙 9개 (비교 6회 · 교환 4회)
2회차 — 14 확정, 남은 힙 8개 (비교 4회 · 교환 3회)
3회차 — 10 확정, 남은 힙 7개 (비교 4회 · 교환 3회)
4회차 — 9 확정, 남은 힙 6개 (비교 4회 · 교환 3회)
5회차 — 8 확정, 남은 힙 5개 (비교 4회 · 교환 3회)
6회차 — 7 확정, 남은 힙 4개 (비교 3회 · 교환 2회)
7회차 — 4 확정, 남은 힙 3개 (비교 2회 · 교환 2회)
8회차 — 3 확정, 남은 힙 2개 (비교 1회 · 교환 2회)
9회차 — 2 확정, 남은 힙 1개 (비교 0회 · 교환 1회)
사용 방법
- 1숫자를 공백이나 쉼표로 나눠 넣습니다. 예제 버튼으로 교과서 자료를 바로 넣을 수도 있습니다.
- 2최대 힙과 최소 힙 중 하나를 고릅니다. 최대 힙은 부모가 자식보다 크거나 같은 상태입니다.
- 3「하나씩 삽입」과 「상향식 heapify」 표에서 각 단계의 비교·교환 횟수와 값이 지나간 자리를 확인합니다.
- 4「배열 ↔ 트리」 표에서 인덱스 i의 부모가 ⌊(i−1)/2⌋, 자식이 2i+1·2i+2인 대응을 확인합니다.
- 5아래 힙 정렬 과정에서 루트를 뽑아 뒤에 쌓으며 정렬되는 모습을 봅니다.
자주 묻는 질문
시간복잡도가 O(n log n)과 O(n)으로 다릅니다. 하나씩 삽입하면 새 값을 맨 뒤에 놓고 부모와 견주며 최대 log i단계까지 올려야 하지만, 상향식은 배열을 통째로 놓고 마지막 내부노드부터 거꾸로 내리기만 합니다. 상향식이 싼 이유는 노드의 절반인 잎을 아예 손대지 않고, 깊이 h인 노드가 많아야 n/2^(h+1)개뿐인데 그중 내려갈 길이 h이기 때문입니다. Σ h·n/2^(h+1)이 2n으로 수렴합니다.
둘 다 올바른 힙이지만 같은 힙일 이유가 없기 때문입니다. 힙 조건은 「모든 부모가 자식보다 크거나 같다」일 뿐이고 형제 사이의 순서는 정하지 않습니다. 예를 들어 4 1 3 2 16 9 10 14 8 7을 상향식으로 만들면 16 14 10 8 7 9 3 2 4 1이지만 하나씩 삽입하면 16 14 10 8 7 3 9 1 4 2가 되며, 둘 다 맞습니다.
아닙니다. 힙이 보장하는 것은 루트가 전체의 최댓값(최소 힙이면 최솟값)이라는 것뿐입니다. 두 번째로 큰 값이 어디 있는지는 정해지지 않고, 배열을 앞에서부터 읽어도 정렬 순서가 아닙니다. 정렬하려면 루트를 뽑고 다시 힙으로 고치는 일을 n번 되풀이해야 하며, 그것이 힙 정렬입니다.
0부터 세는 배열에서 인덱스 i의 왼자식은 2i+1, 오른자식은 2i+2, 부모는 ⌊(i−1)/2⌋입니다. 1부터 세는 교재라면 각각 2i, 2i+1, ⌊i/2⌋가 됩니다. 힙에 포인터가 필요 없는 것이 이 대응 덕분이며, 그래서 중간에 빈자리가 없는 완전 이진트리여야 합니다.
올리기는 한 단계마다 「자식 vs 부모」 비교 1회를 세고, 내리기는 자식이 둘일 때 「둘 중 어느 쪽을 올릴지」 1회와 「부모 vs 고른 자식」 1회를 나눠 셉니다. 자식 고르기를 세지 않는 교재도 있어 값이 갈리므로, 다른 자료와 견줄 때는 규약부터 맞춰야 합니다. 값이 같으면 교환하지 않습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 CLRS「Introduction to Algorithms」Figure 6.3의 예제(4 1 3 2 16 9 10 14 8 7 → 16 14 10 8 7 9 3 2 4 1)와 손으로 따라간 비교·교환 횟수로 했습니다. 예제 버튼의 첫 항목이 그 자료입니다.
- 값이 같을 때는 교환하지 않는 규약을 씁니다. 부모와 자식이 같아도 힙 조건이 이미 성립하기 때문이며, 이 규약이 다르면 교환 횟수가 달라질 수 있습니다.
- 힙 정렬은 제자리 정렬이라 추가 메모리가 거의 없고 최악에도 O(n log n)이지만, 실제로는 캐시 지역성이 나빠 같은 복잡도의 퀵 정렬보다 느린 편입니다.
- 삭제는 루트 삭제(최댓값·최솟값 뽑기)만 다룹니다. 가운데 원소를 지우는 일은 그 자리를 알아야 해서 위치를 따로 기록하는 구조가 필요합니다.
- 한 번에 63개까지만 다룹니다. 과정을 보이는 것이 목적이라 그보다 길면 표가 읽히지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.