우선순위 큐의 비밀
크리스는 퀵 정렬의 '최악의 경우(O(N^2))'가 마음에 걸렸다.
"합병 정렬처럼 항상 빠르면서(O(N log N)), 퀵 정렬처럼 메모리도 안 쓰는(O(1)) 완벽한 정렬은 없을까?"
욕심쟁이 크리스의 요구를 만족시키는 알고리즘이 딱 하나 있다. 바로 힙 정렬(Heap Sort)이다.
하지만 이 녀석을 이해하려면 먼저 '힙(Heap)'이라는 독특한 자료구조를 알아야 한다.
1. 힙(Heap): "대장만 기억한다"
힙은 "최댓값(또는 최솟값)을 빠르게 찾아내기 위해 고안된 완전 이진 트리"다.
쉽게 말해, "부모 노드가 자식 노드보다 항상 큰(Max Heap)" 규칙을 지키는 트리다. (형제끼리는 누가 크든 상관없다. 오직 부모-자식 간의 서열만 엄격하다.)
왜 힙을 쓸까?
힙의 뿌리(Root), 즉 맨 꼭대기에는 항상 가장 큰 값이 위치한다.
우리가 정렬을 할 때 가장 힘든 게 "제일 큰 놈 찾아와"인데, 힙을 쓰면 이 과정이 O(1)이다. 그냥 맨 위를 집으면 되니까!
2. 배열로 트리 만들기
"트리를 구현하려면 노드(Node)랑 포인터를 만들어야 하나요?"
아니오. 힙의 매력은 배열 하나로 완벽하게 트리를 흉내 낼 수 있다는 점이다.
이 공식만 있으면 배열 인덱스만으로 부모 자식을 오갈 수 있다.
3. 힙 정렬의 과정
힙 정렬은 크게 두 단계로 나뉜다.
4. 자바스크립트로 구현하기
코드가 조금 길어 보일 수 있지만, 핵심은 "자식이 나보다 크면 자리를 바꾼다"는 로직 하나다.
// 힙 성질을 만족하도록 수선하는 함수 (Sift Down)
function heapify(arr, length, i) {
let largest = i; // 일단 부모(i)가 제일 크다고 가정
const left = 2 * i + 1;
const right = 2 * i + 2;
// 왼쪽 자식이 부모보다 크면? -> 타겟 변경
if (left < length && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식이 (바뀐) 타겟보다 크면? -> 타겟 변경
if (right < length && arr[right] > arr[largest]) {
largest = right;
}
// 만약 자식 중 누군가가 더 크다면? -> 자리 바꾸기(Swap)
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
// 자리가 바뀐 하위 트리에서도 힙 규칙이 깨졌을 수 있으니 재귀 호출
heapify(arr, length, largest);
}
}
function heapSort(arr) {
const n = arr.length;
// 1. 초기 힙 빌드 (배열을 힙 구조로 변환)
// 맨 뒤의 부모 노드부터 거꾸로 올라오며 heapify를 수행한다.
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 하나씩 꺼내서 정렬
for (let i = n - 1; i > 0; i--) {
// 힙의 루트(최댓값)를 맨 뒤(i)로 보낸다.
[arr[0], arr[i]] = [arr[i], arr[0]];
// 맨 뒤로 간 녀석은 정렬 끝. 나머지(0 ~ i)만 다시 힙으로 만든다.
heapify(arr, i, 0);
}
return arr;
}
heapSort([4, 10, 3, 5, 1]);5. 성능 분석: 완벽하지만 인기 없는 이유
장점: 신뢰의 상징
단점: 퀵 정렬에게 밀리는 이유
핵심 정리
지금까지 배운 모든 정렬 알고리즘(버블, 선택, 삽입, 합병, 퀵, 힙)은 공통점이 있다. 두 데이터를 "비교(Comparison)"한다는 점이다.
그런데 수학적으로 증명된 바에 따르면, 비교 정렬은 아무리 빨라도 O(N log N)의 한계를 넘을 수 없다.
"그럼 비교를 안 하면 되잖아?"
숫자의 자릿수 성질을 이용해서 비교 없이 데이터를 줄 세우는 마법, 기수 정렬(Radix Sort)을 만나러 가보자.