[알고리즘] 힙 정렬(Heap Sort)

오늘은 힙 정렬에 대해 공부하였습니다.

힙 정렬을 알기 전에 먼저 이진트리와 힙에 대해 알아야 합니다.

 

[이진트리]

이진트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 합니다.

완전 이진트리란 이진트리에서 자식 노드들이 왼쪽부터 차곡차곡 채워져 있는 트리를 말하며 완전 이진트리는 마지막 레벨을 제외하고 노드가 모두 채워져 있어야 합니다. 마지막 레벨도 왼쪽부터 채워져 있어야 합니다.

포화 이진트리란 리프 노드를 제외하고 모든 노드들이 2개의 자식 노드를 가집니다. 또한 노드는 왼쪽에서 오른쪽으로 채워져 있습니다. 리프 노드란 자식이 없는 맨 끝에 있는 노드를 말합니다.

 

이진 트리, 완전 이진 트리, 포화 이진 트리

 

[힙]

힙 정렬에는 힙을 사용하게 되는데 힙이란 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조입니다.

 

[힙 정렬]

힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 됩니다.

힙 정렬은 퀵 정렬, 병합 정렬과 마찬가지로 분할 정복 알고리즘의 하나입니다.

최대 힙 - 부모 노드가 자식 노드보다 큰 트트리

최소 힙 - 자식 노드가 부모 노드보다 큰 

 

[힙 정렬 과정]

1. n개의 노드에 대한 완전 이진트리를 구성한다. 이때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 구성한다.

2. 최대 힙을 구성한다. 최대 힙이란 부모 노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모 노드부터 구성하여 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.

3. 가장 큰 수(루트에 위치)를 가장 작은 수와  교환한다.

4. 2와 3을 반복한다.

 

[C언어 코드]

#include <stdio.h>
void HeapSort(int data[], int size)
{
    for (int i = 1; i < size; i++)
    {
        int c = i;        //자식 노드
        do
        {
            //자식 노드에서 1을 빼고 2를 나누면 부모 노드가 나옴
            int parent = (c - 1) / 2;
            //만약 부모 노드보다 자식 노드가 더 크다면 값을 바꿔준다.
            if (data[parent] < data[c])
            {
                int temp = data[parent];
                data[parent] = data[c];
                data[c] = temp;
            }
            //과정이 끝나고 한 레벨 더 올라가서 루트까지 가면서 검사한다.
            c = parent;
        } while (c != 0);
    }
    //위의 과정으로 인하여 가장 큰 값이 루트가 되었으므로
    //루트를 반복적으로 가장 밑으로 내린다면 자연스럽게 오름차순으로 정렬이 됨.
    //크기를 줄여가며 반복적으로 힙을 구성
    for (int i = size - 1; i >= 0; i--)
    {
        //가장 큰 값을 맨 뒤로 보냄
        int temp = data[0];
        data[0] = data[i];
        data[i] = temp;
        int parent = 0;
        int c = 1;
        //힙 구조를 만듬
        do
        {
            c = parent * 2 + 1;
            //자식 중에 더 큰 값 찾기 && 범위를 벗어나지 않도록 막아줌
            if (data[c] < data[c + 1] && c < i - 1)
            {
                c++;    //왼쪽 자식과 오른쪽 자식 중에 더 큰 값을 가진 자식을 c에 담아줌
            }
            //부모보다 자식이 더 크다면 교환
            if (data[parent] < data[c] && c < i)
            {
                temp = data[parent];
                data[parent] = data[c];
                data[c] = temp;
            }
            parent = c;    //한 레벨씩 내려가기 위해 부모를 현재 자식으로 넣어줌
        } while (c < i);    //정렬된 곳까지 가지 않도록 함
    }
}
 
int main()
{
    int arr[10] = { 1, 3, 7, 8, 2, 3, 6, 4, 0, 9 };
    HeapSort(arr, 10);
    for (int i = 0; i < 9; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

 

[출처]

위키 백과

나동빈(안경잡이 개발자) 유튜브, 네이버 블로그