힙 정렬(Heap Sort)

완전이진트리(complete binary tree)

완전 : 루트(root) 노드부터 시작해 왼쪽, 오른쪽 순으로 자식 노드부터 추가하는 모양
이진 : 부모가 가질수 있는 자식의 개수는 최대 2개
트리 : 요소의 상하 관계를 부모(parent)와 자식(child), 자식 간의 관계를 형제(sibling)
루프 : 트리의 첫 노드
리프 : 트리의 마지막 노드

힙(heap)

최대힙 : '부모의 값이 자식의 값보다 항상 큰' 조건을 만족하는 완전이진트리
최소힙 : '부모의 값이 자식 값보다 항상 작은' 조건을 만족하는 완전이진트리

• 최대힙
  

• 자식과 부모 관계식

1. 부모는 a[(i - 1) / 2]
2. 왼쪽 자식은 a[(i * 2) + 1]
3. 오른쪽 자식은 a[(i * 2) + 2]

힙정렬(heap sort)

1. 가장 큰 값이 루트에 위치 하는 특징을 이용하여 정렬하는 알고리즘
2. 가장 큰 값인 루트를 꺼내는 작업 반복하고 그 값을 늘어놓으면 배열 정렬 완료(즉, 선택 정렬을 응용한 알고리즘)

• 루트를 없애고 힙 상태 유지 과정(아래 그림 참고)

1. 루트를 꺼낸다.
2. 마지막 요소를 루트로 이동
3. 자기보다 큰 값을 가지는 자식 요소와 자리를 교환하며 내려가는 작업을 반복,이때 자식의 값이 자기 보다 작거나 리프(leaf)에 다다르면 종료

• 배열의 과정

1. 변수 i의 값을 n-1로 초기화
2. a[0]과 a[i]를 교환(힙의 가장 큰 값의 순서대로 배열의 맨 끝부터 차례로 나열됨)
3. a[0], a[1], ..., a[i - 1]을 힙으로 만듦
4. i의 값을 1씩 줄여나가며 0이 되면 끝, 그렇지 않으면 2번으로 돌아감

허나 초기 상태의 배열이 힙 상태가 아닐 수 있어, 이 과정을 적용하기 전에 배열을 힙 상태로 만들어야함

초기 상태의 배열 힙 만들기

• 과정(아래 그림 참고)

1. 가장 아랫부분 오른쪽 부분트리부터 시작해 왼쪽으로 진행하면서 힙으로 만들어줌
2. 가장 아래부분 단계가 끝나면 하나 위쪽으로 부분트리 범위를 확장
3. 다시 왼쪽으로 진행하면서 부분트리를 힙으로 만들어줌
   

아래 그림과 같이 힙으로 만드는 과정은 부모 노드와 자식 노드중에서 큰 값을 교환하므로 요소의 개수가 n이라면 n/2개만 보면 된다.

힙 정렬의 시간/공간 복잡도

힙 정렬은 선택 정렬을 응용한 알고리즘이며, 또한 불안정 정렬이다. 허나 선택정렬과 다르게 힙 정렬에서는 첫 요소를 꺼내는 것만으로 큰 값이 구해지므로, 첫 요소를 꺼낸 다음 나머지 요소를 다시 힙으로 만들어야 그 다음에 꺼낼 첫 요소도 가장 큰 값을 유지함. 따라서 첫 요소를 선택할때 O(1)이 소요되고, 그 대신 힙 정렬에서 다시 힙으로 만드는 작업은 O(logn)이 소요된다. 이진 검색과 비슷하게 스캔할때 마다 스캔의 범위가 반으로 줄어들기 때문이다. 요소의 개수가 n개 이므로 시간복잡도는 O(nlogn)이다. 공간 복잡도는 병렬 정렬과 다르게 리스트 안에서 swap하므로 O(n)이다.

• 코드

#pragma warning (disable:4996)
#include <stdio.h>
#include <stdlib.h>

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

/* a[left] ~ a[right]의 요소를 힙으로 만드는 함수 */
void heapify(int a[], int i, int n) {
    int cl = 2 * i + 1;  // 왼쪽 자식
    int cr = 2 * i + 2;  // 오른쪽 자식
    int child = (cr <= n && a[cl] < a[cr]) ? cr : cl; // 자식중 큰 값 설정

    if (child <= n && a[i] < a[child]) { // 부모보다 자식이 클 경우
        swap(int, a[i], a[child]); // 교환

        /* 초기 배열 최대힙 과정 : 트리 밑 다시 최대힙 작업 반복 */
        /* 힙정렬 과정: 자식의 값이 자기(루프값) 보다 작거나 리프(leaf)에 다다를때까지 반복 */
        if (child <= n / 2) // 부모 노드 한정하여 반복
            heapify(a, child, n);
    }
}

/* 요소의 개수가 n개인 배열을 힙으로 정렬하는 함수 */
void heapSort(int a[], int n) {

    /* 초기 배열 최대힙으로 */
    for (int i = (n - 1) / 2; i >= 0; i--) // 범위 : 부모 노드
        heapify(a, i, n - 1); // 상향식(가장 아래 노드 오른쪽, 왼쪽, 위쪽 순으로 정렬)

    /* 최대힙 구현후 힙정렬 */
    for (int i = n - 1; i > 0; i--) { // i범위 : 전체
        swap(int, a[0], a[i]); // 루트(가장 큰)값과 리프(마지막 요소) 교환
        heapify(a, 0, i - 1); // 하향식(swap 후 다시 최대힙으로)
    }

}

int main() {
    int nx;
    int* x = NULL;

    scanf("%d", &nx);
    if ((x = (int*)calloc(nx, sizeof(int))) == NULL)
        return -1;

    for (int i = 0; i < nx; i++)
        scanf("%d", &x[i]);

    heapSort(x, nx); // 힙정렬 함수 호출

    for (int i = 0; i < nx; i++)
        printf("%d ", x[i]);

    free(x);
    return 0;
}

• 힙정렬 장점
  시간 복잡도가 O(nlogn)인 빠른 정렬중에 추가적인 메모리가 필요없다.

• 힙정렬 단점
  떨어져 있는 데이터 교환이 발생하므로 불안정적 정렬이다.