Heap
힙은 완전 이진 트리의 일종으로 최댓값, 최솟값을 쉽게 추출할 수 있고, 중복값을 허용한다는 특징을 가진다.
힙 정렬을 이해하기 위해서는 먼저 이진 트리와 완전 이진 트리에 대해 알아야 한다.
이진 트리
컴퓨터가 데이터를 표현할 때 데이터를 각 노드에 담은 뒤 노드를 두 개씩 이어붙이는 구조를 말하며, 모든 노드의 자식 노드가 2개 이하이다. (데이터의 구조가 나무와 닮았다고 해서 트리 구조라고 부른다.)
완전 이진 트리
데이터가 왼쪽부터 빽빽하게 들어가는 이진 트리를 말한다.
힙 생성 알고리즘
힙 정렬을 수행하기 위해서는 힙 생성 알고리즘(Heapify Algorithm)을 사용한다. 힙 생성 알고리즘은 특정한 '하나의 노드'에 대해 수행하는 것으로, 하나의 노드를 제외하고 최대 힙이 구성되어 있는 상태라고 가정한다. 특정 노드 때문에 힙이 붕괴되어 있다면, 그 노드의 자식 값 중에서 큰 값을 자기 자신으로 바꾼다. 이 과정을 자식이 없을 때까지 반복한다.
위 이미지의 경우 부모 노드인 5보다 자식 노드인 7이 커서 힙에 붕괴가 일어났으므로 둘을 바꿔준다.
힙 생성 알고리즘의 시간 복잡도는 O(log N)이다.
힙의 종류
1. 최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2. 최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
힙 정렬 과정
기본적으로 완전 이진 트리를 표현하는 방법은 다음과 같이 그대로 배열에 담는 것이다.
이 상태에서 힙 생성 알고리즘을 실행하면 힙 구조가 될 때까지 알고리즘이 실행된다.
힙 구조가 만들어지면 가장 큰 값인 루트 노드의 값과, 배열의 마지막 값을 교환한다. 가장 큰 값은 배열의 맨 뒤로 가서 정렬이 완료된 것이므로 제외하고, 나머지 배열로 다시 힙 생성 알고리즘을 수행한다. (만약 최소 힙을 구현하려면 반대로 가장 작은 값이 위에 오도록 한다)
이 과정을 모든 값이 정렬될 때까지 반복하면 정렬이 끝나게 된다.
힙 정렬은 힙 생성 알고리즘의 시간 복잡도인 logN이 전체 원소의 개수 n만큼 반복되므로 O(nlogn)의 시간 복잡도를 가진다.
힙 정렬 구현
- 전체 트리 구조를 힙 구조로 바꾼다
- 크기를 줄여가며 반복적으로 힙을 구성한다.(이때 루트 노드와 마지막 노드를 바꾼다)
부모 노드와 자식 노드의 관계
부모의 인덱스 = (자식 인덱스) /2
왼쪽 노드의 인덱스 = 부모 인덱스 2
오른쪽 노드의 인덱스 = 부모 인덱스 2 + 1
function heapSort(arr) {
//1. 전체 트리 구조를 최대 힙 구조로 바꾼다
for (let i = 1; i < arr.length; i++) {
let c = i;
do {
let root = Math.floor((c - 1) / 2);
if (arr[root] < arr[c]) {
//자식 노드가 부모 노드보다 크면
[arr[root], arr[c]] = [arr[c], arr[root]]; //swap
}
c = root; //자식이 부모로 이동
} while (c >= 0);
}
//2. 크기를 줄여가며 반복적으로 힙을 구성한다
for (let i = arr.length - 1; i >= 0; i--) {
//루트 노드와 가장 마지막 노드를 swap
[arr[0], arr[i]] = [arr[i], arr[0]];
let root = 0;
let c = 1;
do {
c = Math.floor(2 * root + 1); //c는 루트의 자식
//자식 중에 더 큰 값을 찾는다.
if (arr[c] < arr[c + 1] && c < i - 1) {
//c가 범위를 벗어나지 않도록 방지
c++; //오른쪽 값이 더 크면 c를 오른쪽으로 이동(왼쪽 오른쪽 중 더 큰 값이 c가 되도록 함)
}
//루트보다 자식이 크면 교환
if (arr[root] < arr[c] && c < i) {
[arr[root], arr[c]] = [arr[c], arr[root]];
}
root = c; //c를 루트로 이동시킨다.
} while (c < i);
}
return arr;
}
console.log(heapSort([1, 18, 397, 5123, 321, 2135, 534]));
참고
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Heap.md
https://www.youtube.com/watch?v=iyl9bfp_8ag
