Blog

C++ 힙 정렬 (Heap Sort), Bottom-up 과 Top-down 구현

April 4, 2014

C++ 힙 정렬 (Heap Sort), Bottom-up 과 Top-down 구현

Heap sort

힙 소트 는 선택 정렬군중 하나로서, 비교 기반 정렬 알고리즘입니다. 선형 시간(Linear Time) 탐색을 이용하는 기본적인 Selection Sort 보다 로그 시간(Logarithmic Time) 복잡도를 가지는 우선순위 큐를 이용함으로써 성능 면에서 더 낫다고 볼 수 있습니다. 비록 대부분의 경우 퀵 소트 보다 느릴지는 몰라도, 최악의 경우에도 O(nlogn) 의 성능을 보장한다는 점에서는 퀵 소트 보다 더 낫습니다. 또한 in-place 알고리즘이기도 합니다. 다만 stable 하진 않습니다.

1. Overview

힙 소트 에 대해 이해하실려면, 기본적으로 Heap 의 동작에 대한 이해가 먼저입니다. Heap 은 다음과 같은 Property 를 가지고 있습니다.

– 1. 부모(Parent)는 항상 자식보다 크거나 같습니다(Max-Heap). 혹은 반대로 항상 자식보다 작거나 같습니다.(Min-Heap)
– 2. 완전 이진트리의 형태여야 합니다.

첫 번째 조건을 Order Property 라고 합니다. Max-Heap 을 구성하는 경우 트리에서 Root 값을 추출하면 지속적으로 최대값만 나오므로 정렬이 가능합니다. Min-Heap 도 마찬가지로 최소값만 나오므로 정렬이 가능합니다.

두 번째 조건을 Structural Property 라고 부릅니다. 힙은 항상 완전 이진 트리(Complete Binary Tree) 여야 합니다. 무슨 말인고 하니, 왼쪽 자식부터 차곡차곡 쌓여야 한다는 뜻입니다. 아래 사진을 보면 이해가 더 쉬우실 겁니다.

힙은 항상 완전 이진트리이므로 부모와 자식간 관계를 구하기가 쉽습니다. 예를 들어, 인덱스가 1부터 시작할 경우 아래와 같은 공식으로 구할 수 있습니다.

Parent = Child / 2;
Left-Child = Parent * 2;
Right-Child = (Parent * 2) + 1;

배열이 0-Base 인 경우는 부모값을 구하기가 조금 더 귀찮아지나 별 차이는 없습니다. 다만 1-Base 로 인덱스를 잡으실 경우, 부모와 왼쪽 자식을 구하는 연산이 2를 곱하거나 나누는 것이므로 시프트 연산 으로 대체하여 쉽게 구현할 수 있다는 장점이 있습니다.

2. Heap Sort Steps

힙소트를 구현하는 방법은, 2단계로 나뉘어 집니다.

1. 힙을 구성하기 (Heapify 라고 보통 부릅니다.)
2. 힙에서 Root 값을 끝까지 추출해서 정렬된 배열 만들기

3. Heapify

힙을 구성하는 방법은 크게 2가지로 나뉩니다. 하나는 Top-Down 방식이고, 다른 하나는 Bottom-up 방식입니다. Top-down 방식이 이해하기 더 쉬우므로 먼저 설명하겠습니다.

Top-down Heap Contsrucntion

Top-down 으로 힙을 구성한다는건, 빈 힙에 차곡차곡 원소를 삽입해 가면서 아래로 확장한다는 뜻입니다. 힙에 원소를 삽입하게 되면, 가장 마지막 자리에 삽입된 뒤 부모 값과 비교하여 차곡차곡 올라오는 Sift-up(Shift 가 아니라 Sift입니다.) 방식을 사용합니다. 그림을 보시겠습니다.

따라서 Top-down 방식으로 힙을 만드는 방법은, 주어진 배열을 비었다고 가정하고 원소의 범위를 1부터 최대값까지 늘려가며 Sift-up 을 호출하게 됩니다. 코드를 보시지요.

void sift_up(int* arr, int root, int current) {

    int parent;

    while (current > root) {
        parent = get_parent(current);
        if (arr[parent] >= arr[current])
            return;

        swap(&arr[parent], &arr[current]);
        current = parent;
    }
}

void heapify_top_down(int* arr, int length) {

    int end = 1;

    while(end < length) {
        sift_up(arr, 0, end++);
    }
}

이렇게 heapify_top_down 함수를 통해 배열 전체를 sift-up 시키면, 힙이 구성됩니다. 그러면, 위쪽부터 순서대로 최대값이 쌓이므로, 이 값을 끝부분과 지속적으로 교환해 주면 정렬된 배열을 얻을 수 있습니다. 일단 코드를 보시죠.

void heap_sort(int* arr, int length) {
    if (arr == nullptr || length <= 1) {
        return;
    }

    // heapify
    heapify_top_down(arr, length);

    // sort
    int end = length - 1;
    while(end > 0) {
        swap(&arr[0], &arr[end--]);
        sift_down(arr, 0, end);
    }
}

주석처리된 sort 부분이 최대값인 arr[0] 과, 끝부분을 지속적으로 교환해 가면서 정렬된 배열을 만드는 코드입니다. 재미있는 사실은, 교환 후에 sift_down 이란 함수를 호출한다는 사실인데, 이건 힙에서 원소의 삭제가 일어나는 과정을 알아야 이해하실 수 있습니다. 아래 그림을 보시겠습니다. 힙에서의 삭제는 최대값을 삭제한 후, 가장 마지막 노드를 루트로 올려 값의 비교가 끝날 때 까지 sift_down 하는 방식으로 진행됩니다.

Bottom-up Heap Construction

사실 위의 Heapify 함수는 조금 더 개선될 수 있습니다. Bottom-up 방식을 이용하면 되는데요. 이 방법은 사실 Top-down 보다는 더 직관적이지 않아 이해하기가 어려우나 성능상 이점이 있습니다. 일단 방법은 이렇습니다. 주어진 배열을 불완전한 힙이라 가정하고, 아랫단부터 위쪽으로 힙을 만들어 가는겁니다. 힙의 가장 마지막 높이(Level) 에서 시작해서, 한 단계씩 높이(Level) 을 올려가면서, 각 노드마다 자신의 하위 노드와 sift-down 을 하게되면 힙을 완성시킬 수 있습니다. 그림을 먼저 보시지요.

void heapify_buttom_up(int* arr, int length) {

    int end = length - 1;
    int current = get_parent(end);

    while(current >= 0) {
        sift_down(arr, current--, end);
    }
}

// Ref : http://en.wikipedia.org/wiki/Heapsort#Pseudocode
void sift_down(int* arr, int current, int last) {

    int left;
    int right;
    int max;

    while((current * 2) + 1 <= last) {
        left = (current * 2) + 1;
        right = (current * 2) + 2;
        max = current;

        if (arr[left] > arr[max]) {
            max = left;
        }

        if (right <= last && arr[right] > arr[max]) {
            max = right;
        }

        if (max != current) {
            swap(&arr[current], &arr[max]);
            current = max;
        } else {
            return;
        }
    }
}

Bottom-up 방식에서는 가장 아랫단부터 시작하기 때문에, 최소한 2/n 개 만큼은 sift-down 을 할 필요가 없습니다. left-node 니까요. 따라서 성능상의 이득이 더 있습니다. 여기 에 의하면 Top-down 방식의 Heapify 는 O(nlogn) 의 성능이 나온다고 합니다. N 개의 원소를 O(logn) 의 복잡도를 가진 삽입 연산으로 넣기 때문이지요. 반면 Bottom-up 방식의 Heapify 는 O(n) 의 성능이 나오는데, 사실 힙소트는 Heapify 뿐만 아니라 Extraction 시간도 고려해야 하기 때문에 두 경우 모두 O(nlogn) 라고 합니다. 왜냐하면, O(nlogn) + O(nlogn)(Top-down) 이나 O(n) + O(nlogn) 이나, O(nlogn) 이기 때문이지요. (Bottom-up 에 대한 성능 증명은 여기로. 간단히 말씀드리면, 높이가 0부터 h까지 있는 힙에서 바텀 업 힙 구성은 2^(h+1) 번의 연산이 필요한데, 이것은 n+1 보다 작으므로 O(n)입니다.)

4. Heap

자료구조인 Heap 도 완전히 이해하셨습니다. 힙은 삽입 연산을 할때 새로운 원소를 마지막 노드에 놓고, sift-up 을 하는겁니다. 반대로 삭제 연산은, 마지막 노드를 루트 노드로 자리를 올리고, 전체 크기를 1만큼 줄인 뒤에 루트노드를 sift-down 하면 됩니다. 위의 코드로 모두 구현할 수 있습니다.

위와 관련된 코드는 https://github.com/ansterd/algorithm/blob/master/cpp/heap-using-array/src/main.cpp 에서 확인하실 수 있습니다. 감사합니다.

References

  1. http://web.cecs.pdx.edu/~sheard/course/Cs163/Graphics/CompleteBinary.jpg
  2. http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/29.HEAPS-II.pdf
  3. http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
  4. http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf