배열을 최대 힙으로 만든 뒤 최댓값을 하나씩 끝으로 보내는 힙 정렬을 막대 애니메이션으로 확인하세요. O(n log n)에 추가 메모리 O(1)인데 왜 잘 안 쓰이는지까지 설명합니다.
알고리즘
배열
비교
0
교환/쓰기
0
스텝
0/665
읽기
0
보조 메모리
0
재귀 깊이
1/1
재생 속도를 늦추고 '한 단계'로 따라가며 의사코드 하이라이트와 막대 색을 비교해 보세요. 회색 막대는 힙에서 이미 빠져나와 정렬이 확정된 자리입니다.
의사코드
build max-heap (siftDown n/2→0)
for end ← n−1 down to 1
swap a[0] ↔ a[end] // 최댓값 확정
siftDown(0, end)
// child = 2·i+1, 2·i+2 중 큰 쪽과 비교
// 부모 < 자식이면 교환하며 내려감
시간 복잡도
| 최선 | O(n log n) |
|---|---|
| 평균 | O(n log n) |
| 최악 | O(n log n) |
| 공간 | O(1) |
| 안정 | X |
힙 정렬은 배열을 완전 이진 트리로 해석해, 부모가 자식보다 항상 큰 최대 힙(max-heap)으로 만든 뒤 시작합니다. 루트(맨 앞)에는 최댓값이 오므로 이를 맨 뒤와 교환해 확정하고, 남은 구간에서 다시 힙 성질을 회복(sift-down)하는 과정을 반복합니다.
힙 구축이 O(n), 이후 n개를 꺼낼 때마다 sift-down이 O(log n)이라 최선·평균·최악 모두 O(n log n)이고, 배열 안에서만 처리되므로 추가 메모리도 O(1)입니다. 최악에서도 안정적인 O(n log n)에 제자리 정렬이라는 희귀한 조합입니다.
그런데도 실무에서 잘 안 쓰이는 이유는 트리의 부모-자식 접근(2i+1)이 배열에서 멀리 떨어져 캐시 효율이 나쁘고, 불안정 정렬이기 때문입니다. 우선순위 큐의 내부 구조로는 지금도 표준입니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.