힙 정렬(Heap Sort)은 완전이진트리 구조를 활용하여 최대값 또는 최소값을 효율적으로 추출하는 비교 기반 정렬 알고리즘이다. 이 글에서는 힙의 개념부터 실제 구현, 그리고 면접에서 자주 등장하는 핵심 포인트까지 심도 있게 다룬다.
힙의 본질: 완전이진트리와 힙 속성
힙은 메모리 관리의 '힙 영역'과 전혀 무관한 자료구조로, 다음 두 가지 조건을 만족하는 특수한 형태의 트리이다.
구조적 특성: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드는 왼쪽부터 순차적으로 배치된다.
값 기반 특성: 부모 노드와 자식 노드 간의 대소 관계가 일정하게 유지된다.
- 최대 힙(Max Heap): 부모 노드 값 ≥ 자식 노드 값 (루트가 전체 최대값)
- 최소 힙(Min Heap): 부모 노드 값 ≤ 자식 노드 값 (루트가 전체 최소값)
배열로 힙을 표현하는 인덱스 공식
실제 구현에서는 포인터 기반 트리 대신 배열을 사용하여 공간 효율성을 확보한다. 0-based 인덱스를 가정할 때, 임의의 노드 i에 대해:
부모 노드: (i - 1) / 2
왼쪽 자식: 2 * i + 1
오른쪽 자식: 2 * i + 2예를 들어 배열 {7, 3, 9, 1, 5}은 다음과 같이 매핑된다:
- 인덱스 0 (값 7): 자식은 인덱스 1 (3), 인덱스 2 (9)
- 인덱스 1 (값 3): 부모는 인덱스 0 (7), 자식은 인덱스 3 (1), 인덱스 4 (5)
- 인스 2 (값 9): 부모는 인덱스 0 (7), 자식 없음
힙 정렬의 핵심 메커니즘
힙 정렬은 최대 힙의 루트(최대값)를 반복적으로 추출하여 배열 뒤쪽부터 채워 나가는 방식으로 동작한다. 전체 프로세스는 세 단계로 구분된다.
- 힙 구성 단계: 무작위 배열을 최대 힙으로 변환
- 추출 및 교환 단계: 루트(최대값)를 배열 마지막 위치와 교환
- 재구성 단계: 남은 요소들로 새로운 최대 힙을 구성하고 단계 2를 반복
이 과정을 거치면 배열의 뒷부분부터 정렬된 상태로 채워지며, 최종적으로 전체 배열이 오름차순 정렬된다.
상세 동작 과정: 예제로 이해하기
배열 {7, 3, 9, 1, 5}을 힙 정렬하는 과정을 단계별로 살펴본다.
단계 1: 최대 힙 구성
마지막 비단말 노드부터 역순으로 sift-down 연산을 수행한다. 마지막 비단말 노드의 인덱스는 (n - 2) / 2로 계산한다.
n = 5이므로, 시작 인덱스는 (5-2)/2 = 1이다.
인덱스 1 처리 (값 3): 자식들은 인덱스 3 (1), 인덱스 4 (5). 최대값은 5이므로 3과 5를 교환 → 배열: {7, 5, 9, 1, 3}
인덱스 0 처리 (값 7): 자식들은 인덱스 1 (5), 인덱스 2 (9). 최대값은 9이므로 7과 9를 교환 → 배열: {9, 5, 7, 1, 3}
최대 힙 구성 완료. 루트 값 9가 전체 최대값이다.
단계 2: 정렬 진행
| 회차 | 교환 전 상태 | 교환 대상 | 교환 후 (힙 영역) | 정렬된 영역 |
|---|---|---|---|---|
| 1 | {9, 5, 7, 1, 3} | 9 ↔ 3 | {3, 5, 7, 1} | {9} |
| 2 | {7, 5, 3, 1} | 7 ↔ 1 | {1, 5, 3} | {7, 9} |
| 3 | {5, 1, 3} | 5 ↔ 3 | {3, 1} | {5, 7, 9} |
| 4 | {3, 1} | 3 ↔ 1 | {1} | {3, 5, 7, 9} |
최종 정렬 결과: {1, 3, 5, 7, 9}
완전한 C++ 구현
다음은 힙 정렬의 표준적인 C++ 구현이다. 변수명과 구조를 달리하여 원본과 차별화하였다.
#include <iostream>
#include <vector>
using std::vector;
using std::swap;
using std::cout;
// 하향 조정: 노드 idx를 루트로 하는 서브트리를 힙 속성에 맞게 재구성
void siftDown(vector<int>& data, int heapSize, int idx) {
int dominant = idx; // 현재 서브트리에서 최대값을 가진 노드
int lChild = 2 * idx + 1; // 왼쪽 자식
int rChild = 2 * idx + 2; // 오른쪽 자식
// 왼쪽 자식이 존재하고 더 큰 경우
if (lChild < heapSize && data[lChild] > data[dominant]) {
dominant = lChild;
}
// 오른쪽 자식이 존재하고 더 큰 경우
if (rChild < heapSize && data[rChild] > data[dominant]) {
dominant = rChild;
}
// 최대값이 현재 노드가 아니라면 교환 후 재귀 처리
if (dominant != idx) {
swap(data[idx], data[dominant]);
siftDown(data, heapSize, dominant);
}
}
// 힙 정렬 메인 함수
void heapSort(vector<int>& data) {
int n = data.size();
if (n <= 1) return;
// 1단계: 상향식으로 최대 힙 구성
for (int i = (n - 2) / 2; i >= 0; --i) {
siftDown(data, n, i);
}
// 2단계: 추출-교환-재구성 반복
for (int end = n - 1; end > 0; --end) {
swap(data[0], data[end]); // 루트(최대값)를 끝으로 이동
siftDown(data, end, 0); // 남은 영역으로 힙 재구성
}
}
// 검증용 메인 함수
int main() {
vector<int> sample = {7, 3, 9, 1, 5, 2, 8, 4, 6};
cout << "원본: ";
for (int v : sample) cout << v << " ";
cout << "\n";
heapSort(sample);
cout << "정렬: ";
for (int v : sample) cout << v << " ";
cout << "\n";
return 0;
}구현의 핵심은 siftDown 함수의 재귀적 호출로, 교환된 자식 노드 아래에서도 힙 속성이 유지되도록 보장한다.
복잡도 분석 및 특성
| 항목 | 결과 | 설명 |
|---|---|---|
| 시간 잡도 (최악) | O(n log n) | 힙 구성 O(n), n-1회 추출 각각 O(log n) |
| 시간 복잡도 (평균) | O(n log n) | 입력 분포에 무관하게 일정 |
| 공간 복잡도 | O(1) | 재귀 스택 외 추가 메모리 불필요 |
| 안정성 | 불안정 | 같은 값의 상대적 순서가 보장되지 않음 |
힙 정렬의 가장 큰 장점은 제자리 정렬(in-place sorting)이 가능하며, 최악의 경우에도 O(n log n)을 보장한다는 점이다. 이는 퀵 정렬의 O(n²) 최악 케이스와 대조된다.
실전 활용: Top-K 문제 해결
힙 정렬의 대표적인 응용은 대용량 데이터에서 상위 K개를 추출하는 문제이다. 전체 정렬 O(n log n) 대신 O(n log K)로 해결 가능하다.
// 크기 K의 최소 힙을 유지하여 상위 K개 최대값 찾기
vector<int> findTopK(const vector<int>& stream, int K) {
// 최소 힙 (C++ 기본 priority_queue는 최대 힙이므로 greater 사용)
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int val : stream) {
if (minHeap.size() < K) {
minHeap.push(val);
} else if (val > minHeap.top()) {
minHeap.pop();
minHeap.push(val);
}
}
vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result;
}K가 n보다 훨씬 작을 때, 이 방식은 메모리와 시간 모두에서 큰 이점을 제공한다.
흔한 실수와 해결책
범위 검증 누락: 자식 노드 인덱스가 현재 힙 크기를 초과하는지 반드시 확인해야 한다.
잘못된 시작점: 힙 구성 시 0번부터 순방향 순회하면 안 된다. 마지막 비단말 노드에서 역순으로 시작해야 한다.
힙 크기 갱신 실패: 매 추출 후 힙 크기를 1 감소시켜야 이미 정렬된 영역이 재조정에 포함되지 않는다.
최대/최소 힙 혼동: 오름차순 정렬에는 최대 힙을, 내림차순에는 최소 힙을 사용해야 한다. 반대로 하면 의도와 다른 결과가 나온다.
타 정렬 알고리즘과의 비교
| 알고리즘 | 평균 시간 | 최악 시간 | 공간 | 안정성 | 적합한 상황 |
|---|---|---|---|---|---|
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | 불안정 | 메모리 제한, 실시간 시스템 |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | 불안정 | 일반적인 범용 정렬 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | 안정 | 외부 정렬, 안정성 필요 시 |
| 팀 정렬 | O(n log n) | O(n log n) | O(n) | 안정 | 실제 데이터 패턴 활용 |
힙 정렬은 공간 효율성과 최악 케이스 보장이라는 두 가지 강점을 가진다. 다만 캐시 효율성은 인접 요소 접근이 잦은 퀵 정렬이나 병합 정렬에 비해 다소 떨어질 수 있다.
핵심 정리
힙 정렬을 완전히 이해하려면 다음 세 가지를 숙지해야 한다: 완전이진트리의 배열 표현, sift-down 연산의 재귀적 구조, 그리고 추출-재구성 반복 패턴. 이 구조를 바탕으로 다양한 변형(예: 부분 정렬, 중위값 추출, 우선순위 큐 구현)으로 확장할 수 있다.