힙 정렬

힙 정렬을 공부하기 전에 힙(Heap)이 무엇인지 알아야 한다. 그리고 힙을 알기 전에는 이진트리(Binary Tree)에 대해서 알고 있을 필요가 있다.

 이진 트리는 모든 노드의 자식 노드가 2개 이하인 노드이다. 이진트리로 완전 이진트리를 구성할 수 있는데 별 다른 것은 아니고 이진트리의 노드가 중간에 비어있지 않고 빽빽이 가득 찬 구조를 완전 이진트리라고 한다. 즉 아래도 완전 이진트리라고 할 수 있다.

이제 힙을 알아보자. 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있고 최소 힙은 그 반대이다.

그런데 힙 구조 안에서 특정 노드 때문에 최대 힙 구조가 붕괴되는 경우가 있다. 다음과 같은 경우이다. (7과 2 때문에 최대 힙 구조가 붕괴되었다.)

이렇게 특정 노드 때문에 힙 구조가 붕괴되는 것을 방지하기 위해서 힙 생성 알고리즘(Heapify Algorithm)을 사용한다. 힙 생성 알고리즘은 특정한 '하나의 노드'에 대해서 수행하는 것이다. 또한 해당 노드를 제외하면 전체 구조는 최대 힙이 구성되어 있는 상태라고 가정한다는 특징이 있다.

 

힙 생성 알고리즘(Heapify Algorithm)은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 또한 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우 또 자식 중에서 더 큰 자식과 자신의 위치를 바꾸어야 한다. 

이러한 힙 생성 알고리즘의 시간 복잡도는 O(log N)이다. 한 번 자식 노드로 내려갈 때마다 노드의 개수가 2배씩 증가하므로 자명하다. 예를 들어 노드의 개수가 1024개라면(2^10) 대략 10번 정도만(아마 그 이하) 내려가도 된다.

 

---

 

그럼 이제 완전 이진 트리에 대해서 힙 정렬을 수행해보자. 완전 이진 트리를 표현하는 가장 간단한 방법은 배열에 그대로 노드를 삽입하는 것이다. 예를 들어 트리가 다음과 같다면 배열로 다음과 같이 표현할 수 있다.

이제 위와 같은 상황에서 모든 원소를 기준으로 힙 생성 알고리즘을 적용해서 전체 트리를 힙 구조로 만들어주면 된다. 이때 데이터의 개수가 N개이므로 전체 트리를 힙 구조로 만드는 복잡도는 O(N * log N)이다. 결과적으로 다음과 같은 최대 힙이 구성된다.

이제부터 실질적인 정렬을 수행할텐데 맨 위에 있는 노드 7을 맨 아래 노드 2와 교환해주면 된다. 그리고 힙 트리의 크기를 1씩 줄여준다.

이제 다시 힙 생성 알고리즘을 수행하고 방금 과정을 반복해서 수행해주면 된다.

모든 정렬이 수행될 때 까지 이 과정을 반복하면 된다. 위에서 말했듯이 힙 생성 알고리즘의 시간 복잡도는 O(log N)이고 전체 데이터의 개수가 N개이므로 힙 정렬의 시간 복잡도는 O(N * log N)이다.

 살펴 본 과정을 코드로 구현해보자.

 

#include <iostream>
using namespace std;

int main() {
    int MAX = 5;
            //    0, 1, 2, 3, 4
    int tree[] = {2, 4, 1, 7, 5};

    for(int i = 1; i < MAX; i++) { // 최초로 힙 구조를 형성
        int child = i;
        do {
            int parent = (child - 1) / 2;
            
            if(tree[parent] < tree[child]) { // 부모 노드가 더 작다면 교환
                int tmp = tree[parent];
                tree[parent] = tree[child];
                tree[child] = tmp; 
            }

            child = parent;
        } while(child != 0);
    }

    for(int i = 0; i < MAX; i++) cout << tree[i] << ' ';
    cout << endl;

    /*
    output
    7 5 1 2 4
    */

    for(int i = MAX - 1; i >= 0; i--) { // 크기를 1씩 줄여가며 힙 구성
        int tmp = tree[0]; // 가장 큰 값을 가장 아래로
        tree[0] = tree[i];
        tree[i] = tmp;

        int parent = 0;
        int child = 1;

        do {
            child = 2 * parent + 1;

            // 두개의 자식 노드 중에 더 큰 노드를 찾는다.
            if(child < i - 1 && tree[child] < tree[child + 1]) {
                child++;
            }

            // 더 큰 자식 노드가 부모 노드보다 크다면
            if(child < i && tree[parent] < tree[child]) {
                tmp = tree[parent];
                tree[parent] = tree[child];
                tree[child] = tmp;
            }

            parent = child;
        } while(child < i);
    }

    for(int i = 0; i < MAX; i++) cout << tree[i] << ' ';
    cout << endl;

    /*
    output
    1 2 4 5 7
    */
}

힙 정렬은 항상 O(N * log N)을 보장할 수 있다는 점에서 강력한 정렬 알고리즘이라고 할 수 있다. 하지만 단순히 속도만 가지고 비교하면 퀵 정렬이 평균적으로 더 빠르기 때문에 힙 정렬이 일반적으로 사용되지는 않지만 CPP에서는 최대 힙, 최소 힙 자료 구조를 사용하는 priority_queue를 이용해서 다양한 알고리즘 풀이에 사용할 수 있다.

 

---

reference

https://youtu.be/iyl9bfp_8ag