힙 정렬 (Heap sort) - 2

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

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

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

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 과정이 필요 없기 때문입니다.

힙을 만드는데의 시간 복잡도는 다음과 같습니다.
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의 값이 가장 최대값 이므로 마지막 값과 바꿉니다.
그리고 마지막값은 정렬된 값으로 간주하고 더 이상 신경쓰지 않아도 됩니다.
그렇게 줄여나간다면 결국 정렬된 상태의 배열이 완성됩니다.

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

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++로 힙 정렬을 구현할 수 있습니다.

#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 봄학기 알고리즘 - 부경대 권오흠 교수님