힙 정렬

Description

힙 정렬은 완전 이진트리 구조로 최대 힙 또는 최소 힙을 만들어 정렬을 이루어 간다
시간 복잡도 = O(N*logN) 이다.

int dataArr[] = { 6, 5, 3, 2, 1, 0, 7 }
에 대해 최대 힙을 만들어 정렬 하는 방식을 알아보자.
최대 힙은 부모가 자식보다 크도록 만들어 나가면 된다.

0번 index는 부모가 없으므로 1번 index부터 부모와 자기 자신의 크기를 비교한다.
1번 index 5와 그 부모인 0번 index 6의 크기를 비교한다.
부모가 자식보다 큰 최대 힙 조건에 적합 하므로 다음으로 넘어간다.

2번 index 3과 그 부모인 0번 index 6과 비교한다.
조건에 맞으므로 다음 으로 넘어간다.

3번 index 2와 부모인 1번 index 5와 비교한다.

4번 index 1과 부모인 1번 index 5와 비교한다.

5번 index 0과 부모인 2번 index 3와 비교한다.

6번 index 7과 부모인 2번 index 3와 비교한다.
자식인 7이 부모 3보다 크므로 서로 자리를 바꾼다.

교환이 이루어졌으므로 2번 index 7과 그 부모인 0번 index 6을 비교한다.
자식인 7이 부모 6보다 크므로 서로 자리를 바꾼다.

가장 큰수인 7이 최상위 부모가 되었고 모든 부모가 모든 자식보다 큰 최대 힙구조로 이루어졌다.
이제 최상위 부모인 7과 마지막 6번 index 3의 자리를 바꾼다.

가장 큰수를 찾아냈으니 이를 제외시키고 다시 한번 0번 index부터 최대 힙 구조를 만드는 반복과정을 거치면 된다.

---

Cord

#include <iostream>

#define LENGTH 7

using namespace std;

// 최대 힙 구성
void maxHeap(int _dataArr[], int _length)
{
    for (int idx = 1; idx < _length; idx++)
    {
        int child = idx;
        while (child != 0)
        {
            int root = (child - 1) / 2; // 자식으로 부터 root 알아내는 공식
            if (_dataArr[root] < _dataArr[child])
            {
                int temp = _dataArr[root];
                _dataArr[root] = _dataArr[child];
                _dataArr[child] = temp;
            }

            child = root;
        }
    }
}

int main()
{
    int dataArr[] = { 6, 5, 3, 2, 1, 0, 7 };
    maxHeap(dataArr, LENGTH);

    for (int idx = LENGTH - 1; idx >= 0; idx--)
    {
        // 가장 큰 숫자를 맨 마지막 원소와 자리 바꾸기
        int temp = dataArr[idx];
        dataArr[idx] = dataArr[0];
        dataArr[0] = temp;
        maxHeap(dataArr, idx);
    }

    // 결과 출력
    string result;
    for (int idx = 0; idx < LENGTH; idx++)
    {
        if (idx == LENGTH - 1)
        {
            result += dataArr[idx] + '0';
        }
        else
        {
            result += dataArr[idx] + '0';
            result += ", ";
        }
    }
    cout << "data = {" << result << " }";
    cout << "\n\n\n\n\n\n\n";

    return 0;
}

---

Result