힙 정렬은 힙(heap) 데이터 구조를 기반으로 수행되는 정렬 알고리즘입니다. 힙은 완전 이진 트리(complete binary tree)의 일종으로, 크게 두 가지 유형으로 나뉩니다.
- 최소 힙(Min-Heap): 루트 노드가 항상 최솟값을 가집니다.
- 최대 힙(Max-Heap): 루트 노드가 항상 최댓값을 가집니다.
힙 정렬의 핵심 원리는 다음과 같습니다. 먼저 배열을 힙 구조로 만든 후, 루트에 있는 요소를 삭제하고 마지막 요소를 루트로 이동시킵니다. 이러한 교환(swap) 과정이 끝나면 배열 전체를 다시 힙 구조로 재구성(re-heapify)해야 합니다. 이 과정을 반복하며 루트에서 요소를 하나씩 제거하면 전체 배열이 정렬됩니다.
힙 정렬의 시간 복잡도와 공간 복잡도
- 시간 복잡도(Time Complexity): O(n log n)
- 공간 복잡도(Space Complexity): O(1)
힙 정렬은 최악의 경우에도 O(n log n)의 성능을 보장하는 안정적인 알고리즘이며, 추가 메모리를 거의 사용하지 않는다는 장점이 있습니다.
입력 및 출력 예시
입력:
정렬되지 않은 데이터 목록: 30 8 99 11 24 39
출력:
정렬 전 배열: 30 8 99 11 24 39
정렬 후 배열: 8 11 24 30 39 99
알고리즘
1. heapify(array, size)
입력 − 데이터 배열과 배열 내 총 요소 개수
출력 − 배열 요소를 사용하여 구성된 최대 힙(max heap)
Begin
for i := 1 to size do
node := i
par := floor(node / 2)
while par >= 1 do
if array[par] < array[node] then
swap array[par] with array[node]
node := par
par := floor(node / 2)
done
done
End
heapify 함수는 각 노드를 부모 노드와 비교하여, 자식이 부모보다 크면 두 값을 교환하는 방식으로 최대 힙을 구성합니다. 이 과정을 모든 노드에 대해 수행하면 배열 전체가 힙 속성을 만족하게 됩니다.
2. heapSort(array, size)
입력: 데이터 배열과 배열 내 총 요소 개수
출력 − 정렬된 배열
Begin
for i := n to 1 decrease by 1 do
heapify(array, i)
swap array[1] with array[i]
done
End
heapSort 함수는 배열의 크기를 하나씩 줄여가며 매번 heapify를 호출하고, 루트(최댓값)를 배열의 마지막 위치와 교환합니다. 이렇게 하면 최댓값부터 차례대로 배열 뒤쪽에 배치되어 오름차순 정렬이 완성됩니다.
C++ 구현 예제
#include<iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 1; i<=size; i++)
cout << array[i] << " ";
cout << endl;
}
void heapify(int *array, int n) {
int i, par, l, r, node;
// 최대 힙 생성
for(i = 1; i<= n; i++) {
node = i; par = (int)node/2;
while(par >= 1) {
// 새 노드가 부모보다 크면 교환
if(array[par] < array[node])
swap(array[par], array[node]);
node = par;
par = (int)node/2;// 검사할 부모 노드 갱신
}
}
}
void heapSort(int *array, int n) {
int i;
for(i = n; i>= 1; i--) {
heapify(array, i);// 매번 힙 재구성
swap(array[1], array[i]);// 첫 번째 요소와 마지막 요소 교환
}
}
int main() {
int n;
cout << "요소 개수 입력: ";
cin >> n;
int arr[n+1]; // 유효 인덱스는 i = 1부터 시작
cout << "요소 입력:" << endl;
for(int i = 1; i<=n; i++) {
cin >> arr[i];
}
cout << "정렬 전 배열: ";
display(arr, n);
heapSort(arr, n);
cout << "정렬 후 배열: ";
display(arr, n);
}
실행 결과
요소 개수 입력: 6
요소 입력:
30 8 99 11 24 39
정렬 전 배열: 30 8 99 11 24 39
정렬 후 배열: 8 11 24 30 39 99
정리
힙 정렬은 힙 구조의 특성을 활용하여 O(n log n)의 일관된 성능을 보여주는 강력한 정렬 알고리즘입니다. 추가 메모리 사용이 거의 없어(O(1)) 메모리가 제한적인 환경에서도 유용하며, 특히 최악의 경우 성능이 중요한 상황에서 퀵 정렬(quicksort)보다 안정적인 선택이 될 수 있습니다.