힙 정렬이란?
힙 정렬(Heap Sort)은 배열을 최대 힙(max-heap)으로 만든 뒤, 가장 큰 값인 루트를 맨 뒤로 빼내는 일을 반복하는 정렬입니다. 추가 배열 없이 제자리에서 정렬하면서도 입력과 무관하게 항상 O(n log n)을 보장합니다.
핵심 한 줄: "최댓값을 빠르게 꺼내 뒤에서부터 쌓는다." 힙은 최댓값을 O(1)에 확인하고 O(log n)에 꺼낼 수 있는 구조라, 이를 n번 반복하면 정렬이 완성됩니다.
먼저, 힙 구조 복습
배열을 완전 이진 트리로 봅니다. 인덱스 i에 대해
- •왼쪽 자식 =
2i + 1, 오른쪽 자식 =2i + 2 - •부모 =
(i - 1) / 2
최대 힙은 "모든 부모가 자식보다 크거나 같다"는 규칙을 지키는 트리입니다. 그래서 루트(인덱스 0)가 항상 전체 최댓값입니다.
동작 원리
1단계. 힙 만들기(build heap). 마지막 부모 노드부터 인덱스 0까지 거꾸로 내려가며 각 노드에 sift-down(heapify)을 적용해 배열 전체를 최대 힙으로 만듭니다. 이 과정은 O(n)입니다.
2단계. 최댓값 빼내기. 루트(arr[0])와 힙의 마지막 원소를 교환합니다. 그러면 최댓값이 배열 끝의 제자리로 갑니다.
3단계. 힙 복구. 힙의 크기를 1 줄이고, 루트에서 sift-down을 한 번 해서 최대 힙 속성을 복구합니다.
4단계. 힙 크기가 1이 될 때까지 2~3단계를 반복합니다. 끝에서부터 큰 값이 차곡차곡 쌓여 오름차순이 됩니다.
알고노트 시각화는 "힙 만들기"와 "꺼내고 복구하기"를 별도 단계로 보여줘 흐름이 한눈에 들어옵니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n log n) |
| 공간 | O(1) |
힙 만들기는 O(n), 이후 n번의 추출이 각각 O(log n)이라 전체는 O(n log n)입니다. 병합 정렬처럼 항상 O(n log n)을 보장하면서도, 별도 배열 없이 제자리에서 정렬해 공간은 O(1)입니다.
예시로 따라가기
[3, 1, 4, 1, 5]를 최대 힙으로 만들면 루트에 5가 옵니다.
- •
5와 맨 끝 교환 → 끝에5확정, 남은 힙 복구 → 루트4 - •
4와 끝에서 두 번째 교환 →...4 5, 복구 → 루트3 - •반복하면
[1, 1, 3, 4, 5]완성
매번 "현재 힙의 최댓값"이 빠져 끝에서부터 정렬됩니다.
자주 하는 실수
- •sift-down/up 혼동: 정렬 단계에서 루트를 내릴 때는 sift-down입니다. 삽입(올리기)과 헷갈리지 마세요.
- •힙 크기 관리: 이미 뺀 원소(끝쪽 정렬된 부분)를 힙 범위에 다시 포함하면 정렬이 깨집니다.
- •자식 인덱스 공식:
2i+1/2i+2범위 초과 검사를 빠뜨리면 배열 밖을 참조합니다.
알고노트에서 직접 확인하세요
배열이 최대 힙으로 만들어지고, 루트가 끝으로 빠진 뒤 힙이 다시 정리되는 과정을 알고노트에서 단계별로 확인할 수 있습니다.