힙 정렬 (Heap sort) - 2

저번 포스팅에서는 힙(Heap)과 max-heapify에 대해 알아보았습니다. 이번 포스팅에서는 직접 1차원 배열을 heap 구조로 변경한 후 힙 정렬을 해보겠습니다.

1차원 배열을 힙(Heap) 으로 만들기

먼저 의사 코드는 다음과 같습니다.

1
2
3
4
BUILD-MAX-HEAP
heap-size[A]<-length[A]
for i <- |length[A]/2| downto 1
do MAX-HEAPIFY(A,i)

i가 A 배열의 길이 / 2 부터 시작하는 이유는 리프 노드에서는 max-heapify 과정이 필요 없기 때문입니다.

BUILD-MAX-HEAP 과정

힙을 만드는데의 시간 복잡도는 다음과 같습니다.
MAX-HEAPIFY 연산의 시간 복잡도는 log(n) 입니다. 그런데 for 문이 n/2 돌기 때문에 n/2*log(n)이며 빅 오로 표기하면 O(n*log(n))이 됩니다.
이는 루트 노드만 고려하여 상당히 러프하게 계산한 것이기 때문에, 정확하게 계산한다면 시간 복잡도는 **O(n)**이 됩니다.

힙 정렬(Heap sort) 하기

힙 정렬은 다음과 같은 순서로 실행됩니다.

  1. 주어진 데이터를 힙으로 만든다
  2. 힙에서 최대값(루트 노드)을 가장 마지막 값과 바꾼다.
  3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 마지막 값은 힙의 일부가 아닌것으로 간주한다.
  4. 루트 노드에 대해서 HEAPIFY(1)한다.
  5. 2~4번을 반복한다.

데이터를 힙으로 만들면 인덱스 1의 값이 가장 최대값 이므로 마지막 값과 바꿉니다.
그리고 마지막값은 정렬된 값으로 간주하고 더 이상 신경쓰지 않아도 됩니다.
그렇게 줄여나간다면 결국 정렬된 상태의 배열이 완성됩니다.

힙 정렬 과정

힙 정렬의 의사 코드는 다음과 같습니다.

1
2
3
4
5
6
HEAPSORT(A)
BUILD-MAX-HEAP(A) // O(n)
for i <-heap-size downto 2 do // n-1 times
exchange A[1] <-> A[i] // O(1)
heap_size <- heap_size -1 // O(1)
MAX-HEAPIFY(A,1) // O(log(n))

총 시간 복잡도는 **nlogn**이 됩니다.

C++로 힙 정렬 구현하기

다음과 같이 C++로 힙 정렬을 구현할 수 있습니다.

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
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <stdlib.h>

#define ITEM_SIZE 10

using namespace std;

void print_arr(int a[], int size) {
for (int i = 0; i < size; i++) {
cout << a[i] << ' ';
}
cout << '\n';
}

void max_heapify(int a[], int size, int idx) {
int left = idx * 2;
int right = (idx * 2) + 1;
int largest = idx;
int tmp = 0;

// 왼쪽 자식 노드와 비교
if (left < size && a[left] > a[largest]) {
largest = left;
}

// 오른쪽 자식 노드와 비교
if (right < size && a[right] > a[largest]) {
largest = right;
}

// 부모 노드보다 자식 노드가 큰 경우 교환
if (largest != idx) {
tmp = a[largest];
a[largest] = a[idx];
a[idx] = tmp;
// 재귀 호출
max_heapify(a, size, largest);
}
}

void build_max_heap(int a[], int size) {
for (int i = size / 2; i > 0; i--) {
max_heapify(a, size, i);
}
}

void heap_sort(int a[], int size) {
int tmp = 0;

build_max_heap(a, size);
for (int count = size - 1; count > 0; count--) {
// 루트 노드를 가장 마지막 노드와 교환
tmp = a[count];
a[count] = a[1];
a[1] = tmp;
// 힙 구조 유지
max_heapify(a, count, 1);
}
}

int main() {
int a[ITEM_SIZE] = { 0, }; // 루트 노드는 1번 인덱스 부터 시작
for (int i = 1; i < ITEM_SIZE; i++) {
a[i] = (rand() % (ITEM_SIZE * 10)) + 1;
}

print_arr(a, ITEM_SIZE);
heap_sort(a, ITEM_SIZE);
print_arr(a, ITEM_SIZE);
return 0;
}

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님

Author

KimJongMin

Posted on

2017-11-19

Updated on

2021-03-22

Licensed under

댓글