힙 정렬 (Heap Sort)

배열을 최대 힙으로 만든 뒤 최댓값을 하나씩 끝으로 보내는 힙 정렬을 막대 애니메이션으로 확인하세요. O(n log n)에 추가 메모리 O(1)인데 왜 잘 안 쓰이는지까지 설명합니다.

알고리즘

배열

크기48
비교 중교환/쓰기피벗/기준읽기정렬 확정
속도50×

비교

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)이 배열에서 멀리 떨어져 캐시 효율이 나쁘고, 불안정 정렬이기 때문입니다. 우선순위 큐의 내부 구조로는 지금도 표준입니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.

자주 묻는 질문

힙이란 정확히 무엇인가요?
완전 이진 트리에 '부모가 자식보다 크거나 같다(최대 힙)'는 규칙을 얹은 자료구조입니다. 배열로 표현하면 인덱스 i의 자식이 2i+1, 2i+2라 포인터 없이 구현됩니다.
힙 정렬이 O(n log n)에 O(1) 공간인데 왜 안 쓰이나요?
부모-자식 접근이 배열에서 떨어진 위치를 오가 캐시 미스가 잦아 실측 속도는 퀵 정렬보다 느립니다. 게다가 불안정 정렬이라 라이브러리 정렬로는 잘 채택되지 않습니다.
힙 정렬은 어디에 쓰이나요?
메모리가 극도로 제한된 환경, 최악 성능 보장이 필요한 경우, 그리고 우선순위 큐를 직접 구현할 때입니다. C++의 std::partial_sort처럼 상위 K개만 뽑는 용도에도 적합합니다.

다른 알고리즘 보기