Heap Sort (힙 정렬)
알고리즘 복습하기 정렬편 6탄
알고리즘 포스팅 하며 복습하기 (정렬편) 📊
힙 정렬이란?
힙 정렬은 배열을 힙(heap)이라는 구조로 만든 뒤, 최댓값을 하나씩 꺼내 뒤에서부터 채워 넣는 알고리즘입니다.
퀵 정렬은 빠르지만 pivot을 잘못 고르면 최악 O(n^2)까지 떨어졌고, 병합 정렬은 최악에도 O(nlogn)이지만 합칠 때 새 배열이 필요했습니다. 힙 정렬은 그 사이에 있습니다. 최악에도 O(nlogn)을 보장하면서 추가 배열 없이 제자리에서 정렬합니다.
힙이란?
힙은 부모와 자식 사이에 크기 관계가 정해진 완전 이진 트리입니다. 두 종류가 있습니다.
- 최대 힙(max heap): 부모가 자식보다 크거나 같다. 루트에 최댓값이 온다.
- 최소 힙(min heap): 부모가 자식보다 작거나 같다. 루트에 최솟값이 온다.
형제 사이에는 아무 규칙이 없습니다. 부모와 자식 관계만 지켜지면 되기 때문에, 정렬된 상태와는 다릅니다. 오름차순으로 정렬하려면 큰 값부터 꺼내 뒤에서부터 채워야 하므로 최대 힙을 씁니다.
트리라고 하지만 따로 노드를 만들지 않고 배열을 그대로 씁니다. 완전 이진 트리는 빈 자리 없이 왼쪽부터 채워지기 때문에, 인덱스만으로 부모와 자식을 계산할 수 있습니다.
왼쪽 자식 = 부모 * 2 + 1
오른쪽 자식 = 부모 * 2 + 2
부모 = Math.floor((자식 - 1) / 2)요소가 7개인 배열이라면 이런 관계가 됩니다.
인덱스 0
/ \
1 2
/ \ / \
3 4 5 6
자료를 찾아보면 왼쪽 자식 = 부모 * 2 로 적힌 글도 많은데, 그건 인덱스 0을 비워두고 1부터 쓰는 방식입니다. 식은 간단해지지만 배열 한 칸을 버려야 합니다. 여기서는 배열을 그대로 정렬해야 하므로 0부터 쓰는 방식을 따랐습니다. 두 방식 모두 맞으니 어느 쪽을 쓰는지만 헷갈리지 않으면 됩니다.
힙 정렬 알고리즘
- 배열 전체를 최대 힙으로 만든다
- 루트(최댓값)를 배열의 맨 뒤와 교환한다 — 맨 뒤 한 칸이 정렬 완료된다
- 정렬된 칸을 제외한 나머지를 다시 최대 힙으로 만든다
- 남은 구간이 하나가 될 때까지 2~3을 반복한다
코드
힙 규칙이 깨진 자리를 고치는 heapify부터 봅니다. 어떤 자리의 값이 자식보다 작으면 자식과 바꿔 아래로 내려보냅니다.
// index 자리의 값이 자식보다 작으면, 제자리를 찾을 때까지 아래로 내려보내는 함수.
//
// size는 "배열에서 힙으로 취급할 범위"다. arr.length와 다를 수 있다.
// 2단계에서 뒤쪽부터 정렬을 확정해 나가는데, 확정된 칸은 힙에서 빼야 하기 때문이다.
const heapify = (arr, size, index) => {
// 부모·왼쪽 자식·오른쪽 자식 셋 중 가장 큰 값이 있는 자리를 찾는다.
// 일단 부모(자기 자신)가 가장 크다고 가정하고 시작한다.
let largest = index;
// 완전 이진 트리를 배열에 눕힌 구조라, 자식의 위치를 계산만으로 알 수 있다.
const left = index * 2 + 1;
const right = index * 2 + 2;
// left < size 를 먼저 확인하는 이유는 두 가지다.
// 자식이 아예 없을 수도 있고, 있더라도 이미 정렬이 끝나 힙에서 제외된 구간일 수 있다.
if (left < size && arr[left] > arr[largest]) {
largest = left;
}
// 왼쪽과 비교해 살아남은 값을 다시 오른쪽과 비교한다.
// 두 번의 비교가 끝나면 largest에는 셋 중 최댓값의 자리가 들어 있다.
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
// 부모가 이미 가장 크다면 이 자리는 힙 규칙을 지키고 있다.
// 아래쪽은 이전 단계에서 이미 정리해 둔 상태라 더 내려갈 필요가 없다.
if (largest === index) {
return;
}
// 더 큰 자식을 부모 자리로 끌어올리고, 부모였던 값은 그 자식 자리로 내려간다.
[arr[index], arr[largest]] = [arr[largest], arr[index]];
// 내려간 값이 새 자리에서 또 자식보다 작을 수 있다.
// 그래서 내려간 자리(largest)를 기준으로 같은 검사를 반복한다.
// 자식이 없는 잎에 닿으면 위의 largest === index 조건에 걸려 멈춘다.
heapify(arr, size, largest);
};size를 인자로 받는 이유는 2단계에서 뒤쪽 정렬된 구간을 힙에서 제외하기 위해서입니다.
const array = [1, 4, 2, 3, 5];
const heapSort = (arr) => {
// ── 1단계: 아무 순서로 들어온 배열을 최대 힙으로 만든다 ──
//
// 잎 노드는 자식이 없으니 그 자체로 이미 힙 조건을 만족한다. 확인할 필요가 없다.
// 그래서 자식을 가진 마지막 노드부터 시작해 루트 쪽으로 거슬러 올라간다.
//
// 거꾸로 올라가는 이유는, heapify가 값을 아래로 내려보내는 함수이기 때문이다.
// 아래쪽이 먼저 힙이 되어 있어야 위에서 내려온 값이 제자리를 제대로 찾아간다.
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
// 아직 정렬을 시작하기 전이라 배열 전체가 힙 범위다.
heapify(arr, arr.length, i);
}
// ── 2단계: 최댓값을 하나씩 꺼내 뒤에서부터 채운다 ──
//
// 최대 힙이므로 루트(arr[0])는 항상 "아직 안 꺼낸 값들 중 최댓값"이다.
// 이 값을 구간의 맨 뒤로 보내면 그 칸은 정렬이 확정된다.
//
// i > 0 인 이유는, 마지막 한 칸만 남으면 그보다 작은 값이 없다는 뜻이라
// 더 할 일이 없기 때문이다.
for (let i = arr.length - 1; i > 0; i--) {
// 최댓값(루트)과 현재 구간의 마지막 칸을 맞바꾼다. arr[i]가 확정된다.
[arr[0], arr[i]] = [arr[i], arr[0]];
// 방금 확정한 칸부터 뒤쪽은 힙에서 제외해야 하므로 size로 i를 넘긴다.
// (i는 확정된 칸의 인덱스이자, 남은 힙의 크기이기도 하다)
//
// 뒤에서 올라온 값이 루트에 앉아 힙 규칙을 깨뜨린 상태이므로 다시 내려보낸다.
heapify(arr, i, 0);
}
return arr;
};
console.log(heapSort(array)); // [1, 2, 3, 4, 5]Math.floor(arr.length / 2) - 1은 자식을 가진 마지막 노드의 인덱스입니다. 그 뒤는 전부 잎 노드라 확인할 필요가 없어서 여기서부터 시작합니다.
시간 복잡도
heapify는 트리의 높이만큼 내려가므로 O(logn)입니다.- 1단계에서 절반의 노드에 대해, 2단계에서 n번 반복하며 매번 호출하므로 전체는 O(nlogn) 입니다.
- 힙의 모양은 값이 아니라 요소의 개수로 정해지기 때문에 최선과 최악이 같습니다.
- 배열 안에서 교환만 하므로 추가 메모리는 쓰지 않습니다.
- 다만 멀리 떨어진 요소끼리 교환하므로 같은 값의 원래 순서는 보장되지 않습니다.
- Big O 표기법은 최악의 경우를 기준으로 표기