정렬 (11) - 힙 정렬 (Heap Sort) (2)

1. Heapify(힙 생성) 알고리즘

• i = 1부터 size/2까지 늘려가며 모든 서브트리를 힙구조로 변경

• i = 1로 설정하는 이유는 Parent & Child의 특수한 관계를 이용하기 위함 (k번째 원소의 부모(k/2), 왼쪽 자식(k*2), 오른쪽 자식(k*2+1) 등. 만약 i = 0부터 시작하면 부모, 왼쪽자식 등이 모두 0이 되기 때문에 연산이 무의미해짐.

• size/2까지 늘리는 이유는 size/2까지의 노드가 내부노드 (자식노드를 가진 노드)이기 때문

• 좌우 자식 노드(arr[c], arr[c+1]) 중 큰 노드를 고르고, 그 노드의 값이 부모노드보다 크면(arr[c], arr[i]) 둘을 Swap하여 힙 구조를 생성함

 

2. Heap Sort (힙 정렬) 알고리즘

• 먼저 배열을 최대 힙 구조로 만듬. 최대 힙 구조에서는 가장 첫번째 원소가 가장 큰 값임.

• 때문에 첫번째 원소를 arr의 가장 끝으로 Swap하여, 최대 값을 찾아냄

• 그리고 이미 정렬된 끝부분을 제외한 나머지 부분을 다시 힙구조로 만듬 (heapify 호출)

• 이 것을 계속 반복하여 가장 큰 원소들을 차례대로 뒤에 담으면 정렬이 완성됨.

 

[그림] 힙정렬 애니메이션

 

3. Heap Sort의 특징

• 시간복잡도 : $O(nlogn)$ 그러나 Quick Sort나 Merge Sort보다는 느림.
• 공간복잡도 : 병합정렬 등과 비교해 새로운 배열을 사용하지 않기 때문에 공간복잡도가 우수함.

 

4. 소스코드

#include <cstdio>

void swap(int *arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void heapify(int *arr, int size, int i) {

    int c = 2 * i + 1;
    // 왼쪽 자식 선택

    if (c < size - 1 && arr[c] < arr[c + 1])
        c++;
    // 오른쪽 자식 존재하면서
    // 오른쪽 자식이 더 크면 오른쪽 자식 선택

    if (c < size && arr[i] < arr[c])
        swap(arr, i, c);
    // 부모보다 자식이 더 크면
    // 둘이 바꿈

    if (c < size / 2)
        heapify(arr, size, c);
    // 내부노드에 한정하여 반복
}

void sort(int *arr, int size) {
    for (int i = size / 2; i >= 0; i--) {
        heapify(arr, size, i);
    }

    for (int i = size - 1; i >= 0; i--) {
        swap(arr, i, 0);
        heapify(arr, i, 0);
    }

}

int main() {
    int arr[] = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    sort(arr, size);

    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i != size - 1) {
            printf(" , ");
        }
    }
    return 0;
}

 

4. Reference