힙 정렬 (Heap Sort)
개yo
이번 포스팅에선 힙 정렬 (Heap Sort)에 대해 알아볼 것이다. 힙 정렬은 이전 포스트에서 다뤘던 퀵 , 병합 정렬 과 마찬가지로 시간복잡도가 O(N *log N) 인 빠른 정렬 알고리즘이다. 힙 정렬을 이해하기 위해선 이진트리, 힙을 이해해야 하기에 이번 포스트에서 함께 알아볼 것이다.
문제
문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
SOL
문제를 해결하기 위해 “힙(Heap)을 이용하여 데이터를 정렬하기”를 생각해 볼 수 있다.
이를 이용한 방법을 힙 정렬 이라고 부른다. 힙정렬은 힙 트리 구조로 이루어저 있어 각각 힙, 트리가 무엇인지 알아야 한다.
완전 이진 트리(Complete Binary Tree)
아래와 같은 구조를 이진 트리라고 한다. 말 그대로 2개의 트리 모양인데 줄기와 가지를 생각하면 된다. 따라서 위 구조는 하나의 줄기에 2개의 가지를 가진 상태다.
특징
- 노드 (1) : 노드(2) (3)의 부모노드
- 루트(Root) 노드
- 노드(2) (3) : 노드 (1)의 자식노드
- 노드(4) (5), 노드(6) : 노드(2) (3)의 자식 노드
- 리프(Leaf) 노드
좀 더 자세하게 말하자면 위 구조는 이진트리 중에서도 완전 이진트리다.
완전 이진 트리는 위와 같이 6개의 데이터가 존재 할때 루트 노드를 시작으로 왼쪽부터 빈 노드없이 채워지는 트리를 말한다.
힙(Heap)
완전 이진 트리에 대해 알아보았으니 이제 힙(Heap)에 대해 알아보도록 하겠다.
힙은 완전이진 트리를 사용하여 최대, 최소힙으로 두가지로 나눠지고 이는 최솟값이나 최댓값을 빠르게 찾아내기 위해 쓰인다.
특징
위와 같은 구조를 힙이라고 하며, 힙 중에서도 최대 힙이다.
- 최대힙은 부모 노드의 값이 자식 노드의 값보다 커야한다.
두번째 예제처럼 최대힙이 붕괴되는 경우에는 자식 노드와 부모 노드를 바꿔야 한다.
- swap(자식 노드(7), 부모 노드(5))
위와 같은 경우를 힙생성 알고리즘이라고 한다.
만약 바꾼 뒤에도 붕괴되는 경우라면 아랫단의 자식과 바꿔야 한다.
- 언제까지??? 붕괴되는 경우가 일어나지 않을 때 까지
위와 같은 힙 생성 알고리즘은 전체 트리의 힙 구조를 가진다. 또한 트리를 보면 알 수 있듯이 자식 노드로 내려갈수록 노드의 개수가 2배씩 증가한다. 이러한 특징은 시간복잡도의 측면에서 봤을 때 O(log N)이 수행된다.
문제
문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라
[ 7 6 5 8 3 5 9 1 6 ]
구현
- 힙을 구성한다.
- 크기를 줄여가며 반복적으로 힙을 구성한다.
- 자식 중에 더 큰 값을 찾는다.
- 루트보다 자식이 크면 교환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
using namespace std;
int num = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6}; // 완전 이진 트리 구조
int main()
{
cout << "정렬 전 : ";
for(auto el : heap)
cout << el << " ";
cout << endl;
// 전체 트리 구조를 최대 힙 구조로 바꾼다.
for(int i=1; i < num; i++)
{
int c = i; // 자식노드
do
{
int root = (c-1) / 2; // 0 index 1회 실행
if(heap[root] < heap[c]) // 0 1
swap(heap[root], heap[c]);
c = root; // index init 1 ~> 0
}
while(c != 0); // c는 0이 되기 때문에 1회만 실행하고 꺼짐
}
cout << "힙 구성 : ";
for(auto el : heap)
cout << el << " ";
cout << endl;
// 크기를 줄여가며 반복적으로 힙을 구성한다.
// root노드의 요소 값을 맨 뒤 리프노드와 바꾼다.
for(int i = num-1; i >= 0; i--)
{
// root 노드와 맨 뒤 leaf노드 스왑
swap(heap[0], heap[i]);
int root = 0; //root 노드
int c = 1; // n 번째 자식노드
do
{
c = 2 * root + 1; // 자식노드 1
// 자식 노드 중 더 큰 값을 찾는다. 왼 오 비교
// 언제까지? 마지막 leaf노드까지~
if(c < i-1 && heap[c] < heap[c + 1])
c++; // 2
// root 노드보다 자식 노드가 크면 스왑
if(c < i && heap[root] < heap[c])
swap(heap[root], heap[c]);
// 재귀적 구조
root = c; // 0으로 초기화
}
while(c < i);
}
cout << "힙 정렬 : ";
for(auto el : heap)
cout << el << " ";
cout << endl;
}
출력
1
2
3
정렬 전 : 7 6 5 8 3 5 9 1 6
힙 구성 : 9 7 8 6 3 5 5 1 6
힙 정렬 : 1 3 5 5 6 6 7 8 9
해설
위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.
힙 구조 구현
1 2 3 4 5 6 7 8 9 10 11 12
for(int i=1; i < num; i++) { int c = i; // 자식노드 do { int root = (c-1) / 2; // 0 index 1회 실행 if(heap[root] < heap[c]) // 0 1 swap(heap[root], heap[c]); c = root; // index init 1 ~> 0 } while(c != 0); // c는 0이 되기에 1회만 실행하고 꺼짐 }
- 자식 중에 루트보다 더 큰 값을 찾는다.
루트보다 자식이 크면 교환한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
for(int i = num-1; i >= 0; i--) { // root 노드와 맨 뒤 leaf노드 스왑 swap(heap[0], heap[i]); int root = 0; //root 노드 int c = 1; // n 번째 자식노드 do { c = 2 * root + 1; // 자식노드 1 // 자식 노드 중 더 큰 값을 찾는다. 왼 오 비교 // 언제까지? 마지막 leaf노드까지~ if(c < i-1 && heap[c] < heap[c + 1]) c++; // 2 // root 노드보다 자식 노드가 크면 스왑 if(c < i && heap[root] < heap[c]) swap(heap[root], heap[c]); // 재귀적 구조 root = c; // 0으로 초기화 } while(c < i); }
마무리
- 힙 정렬은 이전에 다뤘던 병합정렬과 다르게 별도의 추가적인 배열이 필요없어 공간 복잡도 측병에서 효율적이다.
- 시간복잡도가 항상 O(N * log N)을 보장한다.
- 이론적으로 퀸, 병합 정렬보다 더 효율성이 좋다.
- 허나 평균 속도를 보자면 퀵 정렬이 더욱 빠르기에 잘 사용하지 않는다.
- 이론적으로 퀸, 병합 정렬보다 더 효율성이 좋다.
- 루프 내의 코드가 길고, 비효율적인 개시메모리 사용을 하기에 따라 특히 대용량의 데이터를 정렬하기엔 부적절하다.
추가 문제
입력
[ 7 ]
[ 3 1 4 1 5 9 2 ]
힙 정렬의 과정을 출력하는 코드를 작성하여라.
- 단 하향식 힙 정렬을 사용하여라
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<vector>
using namespace std;
// 힙 구조 만들기
// 자식 노드와 비교 후 스왑
// 단 자식 노드에서만
int num = 10;
int heap[] = {26,5,37,1,61,11,59,15,48,19};
void heapify(int i)
{
// 왼쪽 자식노드
int c = 2 *i + 1;
// 오른쪽 자식노드가 있고 왼쪽 자식노드보다 크면
if(c < num && heap[c] < heap[c+1])
c++;
// 부모 노드보다 자식노드가 크면 스왑
if(heap[i] < heap[c])
swap(heap[i], heap[c]);
// num / 2 까지만 왜? why?
// 실질적으로 봐야되는 데이터는 절반으로 나누기 때문
if(c <= num / 2) heapify(c);
}
int main()
{
// 힙 구조 생성
for(int i=num/2; i >= 0; i--)
heapify(i);
// 힙 정렬
for(int i=num; i >=0; i--)
{
cout << "정렬중 ";
for(int j=0; j < num; j++)
{
cout << heap[j] << " ";
}
cout << '\n';
swap(heap[0], heap[i]);
int root = 0;
int c = 1;
do
{
c = 2 * root + 1; // index 1부터
// 범위안에 해당되고 오른쪽 값보다 작으면
if(c < i-1 && heap[c] < heap[c + 1]) c++;
// 하향식으로 스왑
if(c < i && heap[root] < heap[c])
swap(heap[root], heap[c]);
root = c;
}
while(c < i);
}
}