[Algorithm] Heap Sort
Heap Sort
문제
입력값은 다음과 같습니다.
\[N \; a_1 \; a_2 \; a_3 \; ... \; a_N\]
여기서 N은 정렬해야 할 숫자의 개수이고, 뒤에 나온 N개의 숫자들은 오름차순으로 정렬해야 할 숫자들입니다.
이때 N개의 숫자들은 중복이 없고, \(-1000000 \le a_i \le 1000000\) 의 범위를 갖습니다.
예를 들어 입력값이
5 5 1 3 2 4
라고 한다면 출력값은 12345가 되야 합니다.
Bubble Sort(?)
정렬 알고리즘 중 가장 간단한 버블 소트가 있습니다.
숫자 배열을 처음부터 끝까지 모두 검사하며
차례로 제일 큰 원소를 맨 뒤로 보내는 방법입니다.
하지만 for문을 두번 돌기때문에 $O(n^2)$이라는 복잡도를 가집니다.
그래서 N값이 작으면 상관없지만, N값이 매우 클때는 시간이 오래 걸리게 됩니다.
여기서는 Heap Sort로 정렬해보겠습니다.
참고로 뒤에 말하겠지만 Heap Sort의 복잡도는 $O(n\log_2 n)$으로
버블소트보다 성능이 좋습니다.
Heap Sort
Complete binary tree(완전 이진 트리)
일단 Heap Sort는 정렬할 배열을 CBT(Complete Binary Tree)로 간주합니다.
예를 들어 정렬할 배열이 n = {1, 2, 4, 3, 5} 이라면
이걸 CBT로 나타내면 다음과 같습니다.
1을 0번 노드, 2를 1번 노드… 이런식으로 부릅니다.
이렇게 나무 모양(가지가 여러 가지로 나눠지는 모양)으로 생긴 자료구조를 Tree라고 합니다.
0번 노드는 1번, 2번 노드와 연결되있습니다.
이때 0번 노드를 부모, 1번/2번 노드를 자식노드라고 부릅니다.
2번, 3번, 4번 노드는 자식 노드가 없죠.
이처럼 Tree 구조에서는 자식 노드가 없을 수도 있고, 1개만 있을 수도 있고, 2개 이상 있을 수도 있습니다.
그 중, 각각의 노드가 가질 수 있는 자식의 갯수가 최대 2개로 한정된 Tree를 Binary Tree(이진 트리)라 부릅니다.
위 그림은 이진 트리입니다.
참고로 좌측에 있는 자식을 left child, 우측에 있는 자식을 right child라고 부릅니다.
예를 들어 1번 노드는 0번 노드의 left child, 2번 노드는 0번 노드의 right child가 됩니다.
이진 트리에는 최대 2개의 자식 노드가 있을 수 있다고 했는데요,
자식이 없을 수도 있고, left child만 있을 수도 있고, right child만 있을 수도 있고, 모두 있을 수도 있습니다.
CBT(완전 이진 트리)는 이 중 right child만 있는 경우가 없으며,
자식 노드는 왼쪽부터 오른쪽으로 차례로 채워지는 형태의 Tree입니다.
그러니까 1번 노드가 자식이 없는데 2번 노드의 자식이 있을 순 없습니다.
또한 2번 노드가 자식을 갖기 위한 선행 조건은 1번 노드가 2개의 자식 노드를 가져야 한다는 것입니다.
간단한 tree 구조의 용어를 살펴보고 넘어가겠습니다.
tree anatomy(출처: http://www.cs.cornell.edu/courses/cs2112/2015fa/lectures/lecture.html?id=trees)
max-heap
heap sort를 이용하려면 위의 CBT를 max-heap 형태로 바꾸어야 합니다.
max-heap tree란 부모 노드의 값이 자식 노드의 값보다 큰 성질을 가진 tree입니다.
위의 CBT는 0번 노드의 값(1)이 자식 노드의 값(2, 4)보다 작으므로 max-heap이 아닙니다.
max-heap-tree의 값 중 최대값은 항상 0번째 노드의 값이 될 것입니다.
일반적인 CBT를 max-heap tree로 바꾸는 과정은
밑에 있는 노드부터 자식노드와 비교해서 크기를 비교한 후,
자식 노드의 값이 부모 노드보다 크면 자리를 바꿔주면 됩니다.
단, 맨 밑에 있는 노드는 자식이 없으므로 검사하지 않아도 됩니다.
예를 들어 위의 CBT에서 3번/4번 노드는 맨 밑의 노드라 자식노드가 없으므로 검사해줄 필요가 없습니다.
노드가 n개가 있다면 0 ~ n/2 의 노드만 검사해주면 됩니다.
위 CBT를 max-heap으로 바꿔보겠습니다.
이때 5/2 = 2 이고, 2번 -> 1번 -> 0번 노드 차례로 검사해줍니다.
2번 노드부터 살펴보면, 2번 노드는 자식이 없습니다.
즉, 비교해줄 대상이 없으므로 그냥 넘어갑니다.
다음 1번 노드를 살펴보면 left child의 값은 3, right child의 값은 5입니다.
가장 큰 값은 right child인 5이고, 이는 부모노드의 값인 2보다 크므로, 이 둘을 바꿔줍니다.
그 다음 바꿔진 자리 즉, 4번 노드를 검사합니다. 4번 노드는 자식이 없으므로 그냥 넘어갑니다.
다음 0번 노드를 살펴보면, 자식 노드의 값이 5, 4이고 제일 큰 값은 5입니다.
즉, 0번 노드와 1번 노드를 바꿔줍니다.
이제 바꿔진 자식노드 자리를 살펴봅니다. 즉, 1번 노드를 살펴보면 값이 1이고 자식노드의 값은 3, 2입니다.
이 중 큰 값은 3이고 이는 부모 노드의 값인 1보다 큽니다. 즉, 1과 3을 바꿔줍니다.
그 다음 바꿔진 자리 즉, 3번 노드를 검사합니다. 3번 노드는 자식이 없으므로 그냥 넘어갑니다.
이렇게 모든 노드를 검사했고, 만들어진 CBT를 보면 max-heap인걸 볼 수 있습니다.
이제 정렬된 수를 저장할 배열을 새로 만듭니다.
int[] sortedArray = new int[5];
max-heap tree에서 0번째 노드를 빼서 sortedArray의 뒤에서부터 채웁니다.
즉, 가장 큰 값을 빼서 뒤에서부터 채우게 되므로, sortedArray는 자동으로 오름차순 정렬 배열이 됩니다.
이제 남은 문제는 max-heap tree에서 0번째 노트를 뺏을 때의 처리입니다.
다음 max값은 2번 노드의 값인 4가 되는데 그 값은 어떻게 찾아야할까요?
정답은 max값을 빼줄 때마다 새로 max-heap tree를 만들어준다는 것입니다.
예를 들어 위의 CBT에서 5를 빼서 sortedArray에 넣었다면, 현재 상황은 다음과 같습니다.
sortedArray = {null, null, null, null, 5};
(사실 자바에서는 int배열을 만들면 기본값이 0으로 채워지므로 null이 아니라 0이지만 대략적인 설명을 위해…)
Tree의 모양이 매우 어색합니다. 제일 마지막 노드를 0번째 노드자리로 옮겨버립니다.
그리고 이 새로만들어진 CBT를 다시 max-heap tree로 만듭니다.
이때는 새로 바뀐 노드가 0번 노드므로, 0번 노드를 시작으로 바꿔진 자식노드를 차례로 검사하면 됩니다.
0번 노드의 자식들의 값들은 3, 4이고 그 중 큰 값은 4입니다.
그리고 4는 부모노드의 값인 2보다 크죠. 즉 0번 노드와 2번 노드를 바꿔줍니다.
바꿔진 자식노드 자리인 2번 노드를 살펴보면 자식노드가 없으므로 그냥 넘어갑니다.
이제 다시 max-heap tree가 되었고, 같은 과정을 반복합니다.
max값인 0번 노드의 값을 빼서 sortedArray에 넣으면
sortedArray = {null, null, null, 4, 5};
마지막 노드인 3번 노드를 0번 노드에 갖다놓습니다.
0번 노드를 살펴보면, 자식 노드의 값은 3, 2이고 이 중 큰 값은 3입니다.
그리고 3은 0번 노드의 값인 1보다 크므로, 0번 노드와 1번 노드를 바꿔줍니다.
바꿔진 자식 자리인 1번 노드를 살펴보면, 비교할 자식이 없으므로 그냥 넘어갑니다.
다시 max-heap tree가 되었습니다.
max값인 0번 노드를 빼서 sortedArray에 넣습니다.
sortedArray = {null, null, 3, 4, 5};
마지막 노드인 2번 노드를 0번 노드 자리로 옮깁니다.
0번 노드를 살펴보면 자식노드의 값은 1이고, 부모노드의 값인 2가 1보다 큽니다.
즉, 바꿔줄 필요가 없습니다.
다시 max-heap tree입니다.
max값인 0번 노드를 빼서 sortedArray에 넣습니다.
sortedArray = {null, 2, 3, 4, 5}
마지막 노드인 1번 노드를 0번 노드로 옮깁니다.
0번 노드를 살펴보면 자식이 없으므로 그냥 넘어갑니다.
다시 max-heap tree가 되었습니다.
0번 노드를 빼서 sortedArray에 넣습니다.
sortedArray = {1, 2, 3, 4, 5}
tree가 사라졌으므로 과정이 끝났습니다.
sortedArray 자체가 오름차순으로 정렬된 배열이고 이를 출력하기만 하면 됩니다.
복잡도(Time Complexity)
max-heap을 만들어주는 과정을 살펴보면
하나의 노드를 처리해주는데 최악의(가장 오래걸리는) 경우는
0번째 노드에서 가장 밑바닥 노드까지 바꿔주는 경우입니다.
tree의 높이(height)를 $h$라고 한다면 h번 연산이 됩니다.
지금까지 사용한 예시의 CBT는 h=2 입니다.
트리의 높이가 h일때 CBT의 최소 노드 개수는 $2^h$개이고 최대 개수는 $2^{h+1} - 1$입니다.
우리는 복잡도만 볼 것이기 때문에 \(big-O\)로 계산해주면
$O(2^h) == O(2^{h+1} -1)$입니다.
즉, 노드의 개수를 n이라 한다면 다음과 같은 식을 쓸 수 있습니다.
$2^h=n$ 즉, $h=\log_2 n$
아까 한 노드 당 h번 연산이 된다고 했으니 $\log_2 n$만큼 연산이 되는 것이고,
노드의 수는 n이므로, 총 연산 횟수는 $n\log_2 n$이 됩니다.
즉, 복잡도는 $O(n\log_2 n)$이 됩니다.
코드
// heap sort로 풀기
import java.util.Scanner;
public class P2751 {
public static void main(String[] ar){
P2751 ex = new P2751();
Scanner sc = new Scanner(System.in);
int numCount = sc.nextInt();
int length = numCount;
int[] num = new int[numCount];
for(int i=0; i<numCount; i++){
num[i] = sc.nextInt();
}
ex.buildMaxHeap(num, numCount);
int[] sortedArray = new int[numCount];
for(int i=numCount-1; i>=0; i--){
sortedArray[i] = ex.remove(num, length--);
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<numCount; i++){
sb.append(sortedArray[i] + "\n");
}
System.out.print(sb);
}
public void swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public void maxHeapify(int[] arr, int i, int size){
//left child 있을 경우
int left = 2*i+1;
if(left < size){
int tempChild = left;
//right child도 있을 경우 left와 right 둘 중 큰 수와 부모를 비교
int right = 2*i+2;
if(right < size){
if(arr[left] < arr[right]){
tempChild = right;
}
}
//부모 자식 비교해서 자식이 더 크면 스왑
if(arr[tempChild] > arr[i]){
swap(arr, i, tempChild);
}
//마지막 level노드까지 maxHeapify
maxHeapify(arr, tempChild, size);
}
}
public void buildMaxHeap(int[] arr, int size){
for(int i=size/2; i>=0; i--){
maxHeapify(arr, i, size);
}
}
public int remove(int[] arr, int size){
int pop = arr[0];
arr[0] = arr[size-1];
int index = 0;
size--;
while(2*index+1 < size){
int tempChild = 2*index+1;
if(2*index+2 < size){
if(arr[tempChild] < arr[2*index+2]){
tempChild = 2*index+2;
}
}
if(arr[tempChild] > arr[index]){
swap(arr, index, tempChild);
}
index = tempChild;
}
return pop;
}
}
numCount가 정렬해야할 숫자의 개수이고, 정렬해야할 숫자들을
num이라는 int배열에 넣었습니다.
이 num이라는 배열을 buildMaxHeap()을 이용해 max-heap tree를 만들고,
remove()를 이용해 새로 정렬된 배열 sortedArray를 만들고 있습니다.
여기서 buildMaxHeap()를 좀 더 자세히 살펴보겠습니다.
메소드 안을 보면 i=size/2부터 i=0까지 for문을 돌리고 있습니다.
아까 설명했듯이, depth가 가장 큰 노드는 자식이 없으므로 해줄게 없습니다.
그래서 \(depth == h-1\) 인 노드부터
maxHeapify(maxHeap으로 만들어주는 과정)을 해줘야 하므로 size/2부터 시작했습니다.
maxHeapify()를 살펴보면 자식 노드가 있는지 검사하고,
자식 노드가 있으면, 자식 노드 중에 큰 값을 고릅니다.
참고로 부모노드가 i번 노드라면, left child는 2i+1, right child는 2i+2번 노드입니다.
그리고 그 선택된 자식 노드의 값이 부모 노드보다 크면 바꿔줍니다.
이 과정은 마지막 줄에 maxHeapify(arr, tempChild, size)에서 볼 수 있듯이
바꿔준 자식 노드 자리를 계속 검사하여 마지막 레벨의 노드까지 검사합니다.
remove()를 설명드리면,
일단 pop은 리턴할 max값, 즉 arr[0]입니다.
while에서는 새로 바꿔준 0번 노드를 maxHeapify하고 있습니다.
maxHeapify() 메소드를 쓴게 아니라 그냥 while문 내에서 간단하게 maxHeapify하고 있습니다.
새로 바꿔준 0번을 제외한 나머지 노드들은 max-heap tree 상태이기 때문에
새로 바꿔준 0번 노드만 maxHeapify하면 됩니다.
참고로 새로 바꿔준 자식 노드들도 모두 처리해줘야 합니다.