📒 갈무리 - 힙정렬(Heap Sort)&이진트리(Binary Tree)&힙(Heap)

📌 힙정렬이란?

- 완전 이진 트리 구조를 가진 자료구조이다.

- 힙의 특성을 이용하여 정렬하는 방법이다.

- 최솟값 혹은 최댓값 빠르게 가져오기 위해 고안된 방법이다.

 

📌 이진 트리(Binary Tree)

- 컴퓨터 내에서 데이터를 표현할 때 데이터를 각 노드(Node)에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조

- 부모에서 자식으로 뻗어 나가는 구조

- 한 부모가 가질 수 있는 자식 노드의 수는 최대 2개이다.

- 데이터는 부모의 왼쪽부터 들어가게 된다.

트리(Tree) : 가지가 뻗어나가는 것처럼 데이터가 서로 연결되어 있는 구조

루트(Root) : 트리의 최상단 노드

리프(Leaf) : 가장 아래에 있는 노드들

 

📌 완전 이진 트리(Complete Binary Tree)

- 이진 트리의 노드가 중간에 비어있지 않고 모두 채워져있는 구조

 

📌 힙(Heap)

- 힙은 완전히 정렬된 자료구조가 아니라 부모 자식 간에만 부분 적으로 정렬된 자료구조이다.

- 힙은 부모 노드가 자식 노드보다 항상 크거나 작다.

- 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 구조

- 최대 힙과 최소 힙 이 존재한다.

최대 힙 : 부모 노드가 자식 노드보다 큰 힙

최소 힙 : 부모 노드가 자식 노드보다 작은 힙

- 오름차순 정렬일 땐, 최대 힙을 구성

- 내림차순 정렬일 땐, 최소 힙을 구성

- 힙정렬을 하기 위해서는 데이터를 힙 구조(최대 힙 또는 최소 힙)를 갖도록 만들어야 한다.

- 힙정렬을 수행하기 위해서는 '힙 생성 알고리즘(Heapify Algoritm)'을 사용해야 한다.

 

📌 힙 생성 알고리즘(Heapify Algoritm)

- 어떤 노드에 대해서 힙 구조가 붕괴되었을 때 그 노드의 자식들 중에서 더 큰 값 또는 더 작은 값을 부모로 변경하는 알고리즘

- 모든 정점에 대해 힙 생성 알고리즘을 수행한다면 힙 구조가 된다.

- O(logN)의 시간 복잡도를 갖는다.

- 힙 생성 알고리즘을 전체 원소의 개수만큼 반복해서 수행하면 정렬이 이루어지기 때문에 힙 정렬의 시간 복잡도는 O(N*logN)이 된다.

- 상향식과 하향식 구현 방식이 있다.

- 상향식 : 아래쪽에서 위쪽으로 올라가며 힙 구조를 만드는 방식

- 하향식 : 위에서 아래쪽으로 내려가며 힙 구조를 만드는 방식

- 상향식이냐 하향식이냐에 따라 힙 구조가 다를 순 있지만, 힙 구조를 만드는 것이 목적이기 때문에 어떤 방식을 사용하느냐는 상관이 없다.

 

💡 TIP

실제로는 데이터의 개수를 반으로 나눈 횟수만큼만 수행을 하더라도 힙 구조를 만들 수 있기 때문에 실제 시간 복잡도는 O(n/2*logN)이 될 수 있다.

 

📌 힙정렬 진행 순서

1. n개의 노드에 대해 완전 이진 트리를 구성한다.

2. 최대 힙 또는 최소 힙을 구성한다.

3. 가장 큰 수(루트 노드)를 가장 작은 수와 교환한다.(최대 힙 기준)

4. 2와 3을 반복한다.

 

📌 직접 구현해 보자...

// C#
        public void HeapSort(int[] data)
        {
            int root;
            int c;
            for (int j = data.Length - 1; j >= 0; j--)
            {
                for (int i = 1; i <= j; i++) // 전체 트리 구조를 힙구조로 변경
                {
                    c = i;
                    while (c != 0) // 최상단 부모와 비교할 때까지
                    {
                        root = (c - 1) / 2;
                        if (data[root] < data[c])
                        {
                            Swap(ref data[root], ref data[c]);
                        }
                        else
                        {
                            break;
                        }
                        c = root;
                    }
                }
                Swap(ref data[0], ref data[j]); // 가장 큰 값과 마지막 값을 변경
            }

        }

        public void Swap(ref int number1, ref int number2)
        {
            int temp = number1;
            number1 = number2;
            number2 = temp;
        }
        // 가독성을 위해 각 기능마다 함수로 분리하면 좋지만, 지금은 편의상 간단하게 구현함

 

📌 힙정렬의 특징

- 병합정렬, 퀵정렬과 마찬가지로 O(N*logN)의 시간 복잡도를 갖는다.

- 병합정렬과는 다르게 별도의 추가적인 배열이 필요하지 않기 때문에 메모리 측면에서 보다 효율적이다.

- 항상 O(N*logN)의 시간 복잡도를 보장한다는 점에서 강력한 정렬 알고리즘이라 할 수 있다.