[ 정렬 ] 힙 정렬 (Heap Sort) (C++)

이번 글에서는 힙정렬(Heap Sort)에 대해서 다뤄보겠다.

먼저 힙 정렬은 '완전이진트리'를 기반으로 구현되는 정렬 방식이다.

완전 이진트리는 모든 Node가 빈 공간 없이 순차적으로 채워져 있는 Tree를 말한다.

즉 위와 같은 Tree를 '완전이진트리'라고 한다.

힙정렬은 완전이진트리 기반으로써, 배열을 완전이진트리 꼴로 생각하고 계산을 한다.

실제로 Left_Child, Right_Child, Parent_Node 등을 특별한 자료구조를 이용해서 생성하는 것은 아니고, Index번호를

마치 완전이진트리 처럼 생각하고 사용한다. 이게 무슨말일까??

완전이진트리는 다음과 같은 특징을 갖는다.

"왼쪽 자식의 노드 번호 = 부모 노드의 번호 * 2 , 오른쪽 자식의 노드 번호 = 부모 노드의 번호 * 2 + 1"

or

"왼쪽 자식의 노드번호 or 오른쪽자식노드 번호 / 2 = 부모 노드의 번호" 가 된다.

위와 같이 계산이 가능한 것이다. 하지만, 배열을 위와 같이 생각하기에는 치명적인 문제가 하나가 있다.

배열의 크기를 N으로 잡았다고 가정 할 때, 우리가 사용하는 배열의 Index번호는 0번부터 N-1번까지 사용을 한다.

그렇다면 위와 같은 계산이 가능할까?? 가능하지 않다. 따라서 힙 정렬은 배열의 0번은 비워두고, 1번부터 N번까지 배열을

사용하는 방식으로 계산한다. '완전이진트리'꼴이기 때문이다 !

그렇다면 이제부터 힙정렬의 구체적인 방법을 알아보자.

1. 힙을 만들어준다.

   - 여기서 힙이라는게 뭘까? 2가지가 존재한다. 최대힙 혹은 최소힙.

     최대힙이라는 것은 "부모 노드의 값이 자식 노드의 값보다 큰 완전이진트리 꼴"

     최소힙이라는 것은 "부모 노드의 값이 자식 노드의 값보다 작은 완전이진트리 꼴" 로 만들어 주는 것이다.

   - 본인은 오름차순을 기준으로 하기 때문에 최대힙을 구현할 것이다.

2. Root Node와 가장 마지막 Node의 값을 Swap 해준다.

3. Root Node에 있는 값을 다시 제자리로 보내준다. 이 때, 순차적으로 N-1, N-2, N-3번... Node까지만 비교한다.

   - 왜그럴까? 우리는 2번 과정에서 RootNode와 가장 마지막 Node의 값을 Swap 해주었다.

     만약, 1번 과정에서 최대힙을 만들었다면 완전이진트리의 부모 노드의 값이 자식 노드의 값보다 더 큰 꼴일 것이고

     당연하게도 Root Node의 값은 가장 큰 값이 되있을 것이다. 이 상태에서 Root Node와 가장 마지막 Node를 바꿔주었

     으니, Root Node에는 굉장히 작은 값이 가 있을 것이고 가장 마지막 Node에는 가장 큰값이 와 있을 것이다.

     즉, 가장 마지막 Node에는 가장 큰 값이 정렬된 자기 자리에 가 있는 형태이다. 따라서, 더 이상 건드릴 필요가 없는

     것이다.

그림을 보면서 차례차례 알아보자.

위와 같은 배열이 있다. 이를 완전이진 트리 꼴로 나타내보자 ! 

1. 힙을 만들어 주자 ! (본인은 오름차순 기준이므로 최대힙을 만들겠다. 최대힙 : 부모의 값 > 자식의 값)

- 힙을 만드는 구체적인 순서는 다음과 같다.

   1) 2번 Index부터 N번 Index까지 반복하는데, 각각의 부모 Node와 비교해서 만약 자식의 값이 더 크다면,

      부모 Node와 값을 바꿔주고 다시 이를 반복.

      - 2번 Index부터 시작하는 이유는, 부모가 있기 위한 최소의 Index번호는 2번 이기 때문이다.

        1번 Index는 Root Node로써 부모가 없다 !

이 때 값을 비교해보면, 자식의 값이 더 크기 때문에 부모와 Swap을 해주고 Cur_Idx 또한 바꿔준다.

즉, 다음과 같은 상황이 될 것이다.

3번 Index의 경우 위와 같은 과정을 해봤자, 자식의 값이 더 작기 때문에 그대로일 것이다.

4번 Index('7'의 값)에 대해서 실시해보자.

더 크기 때문에 값을 바꿔주고 Cur_Idx 또한 바꿔준다.

또 비교 했을 때, 또 더 큰 값을 가지기 때문에 다시한번 바꿔준다.

이런식으로 모든 Node들에 대해서 쭉 Swap을 하고 비교를 하다보면 결국 아래와 같은 최대힙이 완성될 것이다.

2. 이제 Root Node와 가장 마지막 Node의 값을 바꿔준다.

3. 정렬된 가장 큰 값이 저장된 마지막 노드를 빼고 N-1번까지 비교해서 RootNode에 있는 값인 '3'을 제자리를 찾아준다.

    본인은 재귀를 통해서 구현하였는데, 함수명은 Heapify() 이다.

    매개변수로, (int Current, int N)이 오게 되는데, Current는 현재 Index번호, N은 탐색 영역이다.

    즉, 위의 경우에서는 첫 호출에 매개변수를 (1, N-1)로 호출할 것이다.

    이것이 의미하는 것은 현재 '1'번 Index에 있는 값을 제자리로 돌려보낼 건데 비교는 N-1번까지만 할게요 !

    라는 의미이다. N-1번까지만 비교하는거는 위에서 수없이 말했다 !

    구체적은 제자리를 찾는 과정은 다음과 같다.

    1) 현재 Index(매개변수 Current)가 가진 값과 왼쪽 자식 노드의 값을 비교한다.

        이 때, 왼쪽 자식 노드의 값이 더 크다면, 현재 Index에 있는 값은 최대힙의 조건에 위배되는 상황인 것이므로

        왼쪽 자식 노드의 값에 현재 Index를 설정해준다. 여기서 바로 바꿔버리면 안된다 ! 왜냐하면 오른쪽 자식 노드 와도

        비교를 해봐야 하기 때문이다.

    2) 현재 Index가 가진 값( 1)의 과정에 의해서 왼쪽 자식 Node의 값이 현재 Index로 이미 갱신이 되었을 수도 있음 !)

        과 오른쪽 자식 노드의 값을 비교해서 오른쪽 자식 노드의 값이 더 크다면, 결과적으로 부모, 왼쪽자식, 오른쪽자식을

        비교했을 때 오른쪽 자식이 제일 큰 값이라는 의미이기 때문에 오른쪽 자식 노드의 값을 현재 Index로 설정 !

    3) 매개변수로 호출된 Current 값과 현재 Index값을 Swap 후 ! 현재 Index로 다시 재귀호출 !

    그림으로 나타내면 다음과 같다.

위의 그림에서 빨강색 동그라미는 현재 Index값을 의미한다. 여기서 왼쪽 자식 노드의 값인 7과 비교를 한다.

7이 더 크기 때문에 현재 Index가 아래와 같이 설정될 것이다.

여기서 바로 스왑하는 것이 아닌 ! 오른쪽 자식과도 비교를 해준다. 즉, 현재 Index와 오른쪽 자식 비교를 하는 것이니

'7' 과 '5'를 비교하는 꼴이 된다. 비교를 했을 때, 7이 더 크기 때문에 현재 Index의 값에는 변화가 없게 된다.

이 후, 매개변수로 호출된 Current값과, 현재 Index값이 다르기 때문에 Swap 후 재귀호출 !

다음과 같아진다.

재귀를 호출한 상태이다. 여기서 위와 같이 왼쪽 자식 , 오른쪽 자식과 비교를 하고 Swap을 한 후에 재귀를 호출하면 다음과

같아질 것이다.

여기서 또다른 변화가 생기게 될까?? 당연히 생기겠지? 밑에 9가 있는데???? 라고 하면 안된다.

아까도 말했듯이 9는 이미 정렬된 놈이기 때문에 건드릴 필요가 없다. 따라서, 위의 상태가 '3'이 제자리로 찾아온 상태가 된다.

위의 트리를 보면 자연스럽게 다시 최대힙과 같은 꼴로 만들어 졌다.

이 상태에서 Root 값과 N -1의 값을 Swap 하면 다음과 같아진다.

이제부터 위와 같은 과정으로 또 0 을 제자리를 찾아가게 만들면 되는 것이다.

이 때 우리가 눈여겨 봐야할 것은 '7'과 '9'가 정렬이 되었따는 것이다! 즉, 위의 과정을 계속 반복하면 결과적으로

오름차순으로 트리가 정렬된 다는 것을 알 수 있다.

코드를 보면서 정리를 해보자.

void Build_Heap()    // 주어진 배열을 최대힙으로 만드는 함수이다.
{
    for (int Cur_Idx = 2; Cur_Idx <= MAX; Cur_Idx++)    // 1번은 부모가 없으므로 2번부터 시작.
    {
        while (Cur_Idx > 1)                        // Root가 아닐 때 까지 반복하는데...
        {
            int Parent_Idx = Cur_Idx / 2;         // 부모 인덱스와 비교하기 위해서 부모 인덱스 값 설정.
            if (Arr[Cur_Idx] > Arr[Parent_Idx])    // 만약, 부모보다 값이 더 크다면??
            {
                swap(Arr[Cur_Idx], Arr[Parent_Idx]);    // 값을 바꿔주고
                Cur_Idx = Parent_Idx;                // 현재 Index도 부모 Index로 바꿔주고 비교 계속해서 진행.
            }
            else break;                        // 부모 Index가 더 큰 경우에는 변화가 일어나지 않으므로 종료.
        }
    }
}

void Heapify(int Current, int N)    // 제자리를 찾아가게 만드는 함수(첫 Index, 탐색범위)
{
    int Cur_Idx = Current;            // 현재 Index
    int Left_Child = Current * 2;        // 왼쪽 자식 Index번호
    int Right_Child = Current * 2 + 1;    // 오른쪽 자식 Index번호

    if ((Left_Child <= N) && (Arr[Left_Child] > Arr[Cur_Idx])) Cur_Idx = Left_Child;    // 왼쪽자식과 비교
    if ((Right_Child <= N) && (Arr[Right_Child] > Arr[Cur_Idx])) Cur_Idx = Right_Child;  // 오른쪽자식과 비교
     
    if (Cur_Idx != Current)        // 만약 변화가 생겼다면
    {
        swap(Arr[Cur_Idx], Arr[Current]);    // Swap 후
        Heapify(Cur_Idx, N);        // 재귀호출
    }
}

void HeapSort()            // Main에서 호출되는 HeapSort
{
    Build_Heap();            // 최대힙으로 먼저 만들어주고
    for (int i = MAX; i >= 2; i--)
    {
        swap(Arr[i], Arr[1]);    // Root와 정렬이 안된 마지막 Node 교환.
        Heapify(1, i - 1);       // 제자리 찾아가기 !    
    }
}

# 시간복잡도

- 먼저, 최대힙으로 완전이진트리를 구현하는데 걸리는 시간은 얼마일까??

   모든 노드를 비교해서 부모 값을 더 큰 값으로 만들고 자식의 값을 더 작게만들기 때문에 N -1번 탐색을 해야 할 것이다.

   즉, 빅오 표기법으로 표현하면 이 되는 것이다.

   그렇다면, RootNode와 마지막 Node를 Swap 후 제자리로 찾아가는 과정은 얼마가 걸리게 될까??

   완전이진트리도 Quick, Merge와 같은 원리에 의해서 logN 만큼 내려오면서 탐색을 진행할 것이다.

   그런데 내려오면서 왼쪽자식노드, 오른쪽자식노드 2개를 비교했네? 그러면 2 x logN 이 되는것이다.

   즉, 결과적으로 말하자면 2logN + (N-1)번 만큼의 탐색을 평균적으로 한다는 것이다.

   따라서 시간복잡도를 빅오 표기법으로 표현하면 이 되는 것이다.

   최악의 경우 최선의 경우 모두 위와 같은 시간복잡도를 갖게 된다.

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
 
#define MAX 100
using namespace std;
 
int Arr[MAX + 1];
bool Flag[10000];
 
void Print()
{ 
    cout << "##########################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 1; i <= MAX; i++)
    {
        printf("%3d ", Arr[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << "##########################################################################################################" << endl;
    cout << endl;
}
 
void Build_Heap()
{
    for (int Cur_Idx = 2; Cur_Idx <= MAX; Cur_Idx++)
    {
        while (Cur_Idx > 1)    // if Current Idx is Not Root. Do
        {
            int Parent_Idx = Cur_Idx / 2;
            if (Arr[Cur_Idx] > Arr[Parent_Idx])
            {
                swap(Arr[Cur_Idx], Arr[Parent_Idx]);
                Cur_Idx = Parent_Idx;
            }
            else break;
        }
    }
}
 
void Heapify(int Current, int N)
{
    int Cur_Idx = Current;
    int Left_Child = Current * 2;
    int Right_Child = Current * 2 + 1;
 
    if ((Left_Child <= N) && (Arr[Left_Child] > Arr[Cur_Idx])) Cur_Idx = Left_Child;
    if ((Right_Child <= N) && (Arr[Right_Child] > Arr[Cur_Idx])) Cur_Idx = Right_Child;
     
    if (Cur_Idx != Current)
    {
        swap(Arr[Cur_Idx], Arr[Current]);
        Heapify(Cur_Idx, N);
    }
}
 
void HeapSort()
{
    Build_Heap();
    for (int i = MAX; i >= 2; i--)
    {
        swap(Arr[i], Arr[1]);
        Heapify(1, i - 1);
    }
}
 
int main(void)
{
    srand((unsigned)time(NULL));
    for (int i = 1; i <= MAX; )
    {
        Arr[i] = rand() % 300 + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            i++;
        }
    }
 
    cout << "[ Initialize Array State ]" << endl;
    Print();
    HeapSort();
    cout << "[ After Sorting Array State]" << endl;
    Print();
 
    return 0;
}