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

힙 정렬은 이진 힙(binary heap) 자료구조를 사용하는 정렬 방법이다.

힙이란?

Heap은 최댓값 및 최솟값을 빠르게 찾아내기 위해 고안된 자료 구조로, 완전이진트리(complete binary tree)이면서 힙 속성(heap property)를 만족한다.

• max heap(최대 힙) property : 부모 노드는 자식 노드보다 크거나 같다.
• min heap(최소 힙) property : 부모 노드는 자식 노드보다 작거나 같다.

완전이진트리 (Complete binary tree)

이진 트리란, 각 노드가 최대 2명의 자식만을 갖는 트리를 말한다.

완전이진트리를 설명하는 데 앞서 정 이진 트리(full binary tree)에 대해서도 설명할 필요가 있다.

• full binary tree : 모든 레벨의 노드가 2개의 자식 노드로 꽉 차 있는 트리
• complete binary tree : full binary tree와 달리 가장 오른쪽부터 연속된 몇 개의 노드가 비어 있을 수도 있다.

정 이진트리는 완전이진트리이기도 하다. 그러나 완전이진트리가 정 이진트리이지는 않다. 또, 오른쪽이 아닌 왼쪽의 자식 노드가 비어있는 트리는 완전이진트리가 아니다.

힙은 완전이진트리이면서 부모 자식 간의 대소관계를 만족해야 한다. 이 때 힙의 경우의 수는 여러 개가 존재할 수 있기 때문에 서로 다른 힙이 존재할 수 있다. 즉 힙은 유일하지 않다.

힙의 배열 표현

힙은 간단하고 규칙적인 구조를 가지고 있어 배열로 표현이 가능하다.

• 루트 노드 : $A[1]$
• $A[i]$의 부모노드 : $A[i/2]$
• $A[i]$의 왼쪽 자식노드 : $A[2i]$
• $A[i]$의 오른쪽 자식노드 : $A[2i+1]$

힙 정렬에서는 트리를 최대 힙 또는 최소 힙 트리로 만들어 정렬을 한다. 오름차순 정렬을 위해선 최대 힙을 구성하고, 내림차순 정렬을 위해서는 최소 힙을 구성한다. 아래는 최대 힙을 구성해 오름차순 정렬을 하는 힙정렬 소스코드이다.

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapsort(int arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

최대 힙 정렬에서 heapify 함수는 트리의 일부분이 주어졌을 때 두 자식들 중 더 큰 쪽이 나보다 크면 서로 자리를 교체한다. 이를 heapsort에서 순환하며 호출하면서 크기가 큰 노드는 점점 루트노드를 향해 올라가게 된다.

• 힙 정렬의 작동 구조

1. heapsort 함수에서 순환하며 heapify 함수를 호출하며 주어진 배열을 최대 힙으로 만든다.
2. heapsort 함수의 두번째 for문에서는 n-1번째(배열의 끝)부터 시작하여 최대값(루트)을 배열의 맨 뒤로 이동시킨다. 이를 반복하면 배열의 가장 큰 값이 맨 뒤에 위치하게 된다.
3. 이때 배열의 가장 마지막으로 이동시킨 값은 힙의 일부가 아닌 것으로 간주하고 제외한다.
4. 루트노드에 대해서 heapify를 호출하는 것을 반복한다.

힙 정렬을 통해 주어진 트리를 최대 힙 구조로 만들게 되면 항상 최댓값이 루트에 존재한다. 이를 배열로 옮기는 과정이 heapsort 함수의 2번째 for문이다.

힙 정렬은 $O(n log n)$의 시간 복잡도를 갖는다. 이진 트리를 최대 힙으로 만드는 데에 트리의 높이($O(logn)$)의 시간이 걸리고, 이를 정렬하는데 $O(n)$의 시간이 걸린다.

참고자료
힙 정렬(heap sort) / https://youtu.be/ihyg2OR8IR0