힙과 힙 정렬

힙(Heap)은 완전 이진 트리 형태로 구성된 자료구조로, 항상 부모 노드가 자식 노드보다 크거나(최대 힙) 작도록(최소 힙) 유지되는 성질을 가지고 있습니다. 힙 자료구조를 이용한 힙 정렬(Heap Sort)은 매우 효율적인 정렬 알고리즘 중 하나로, 시간 복잡도가 O(n log n)입니다. 이번 글에서는 힙의 개념부터 힙 정렬의 구현까지 설명하고, Java와 C로 구현 예제를 제공합니다.

힙이란?

힙은 특정한 조건을 만족하는 완전 이진 트리입니다. 힙에는 두 가지 종류가 있습니다:

1. 최대 힙(Max Heap): 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 구조입니다. 따라서 루트 노드는 힙에서 가장 큰 값을 가집니다.
2. 최소 힙(Min Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 구조입니다. 따라서 루트 노드는 힙에서 가장 작은 값을 가집니다.

힙의 주요 용도 중 하나는 우선순위 큐(Priority Queue)입니다. 우선순위 큐는 삽입과 삭제 작업이 빈번하게 발생하는 상황에서 효율적으로 처리할 수 있으며, 힙을 사용해 구현할 수 있습니다.

힙 정렬(Heap Sort)이란?

힙 정렬은 힙 자료구조를 이용한 정렬 알고리즘입니다. 기본적으로 최대 힙을 사용하여 정렬하고자 하는 데이터를 힙에 넣고, 힙에서 하나씩 데이터를 꺼내어 정렬하는 방식입니다. 힙 정렬은 다음과 같은 두 단계로 이루어집니다:

1. 힙 구축(Build Heap): 주어진 데이터를 최대 힙 또는 최소 힙으로 변환합니다.
2. 정렬(Sort): 힙에서 가장 큰(또는 작은) 값을 루트에서 꺼내고, 남은 요소들로 힙을 재구성하여 정렬합니다.

힙 정렬의 시간 복잡도는 최악, 평균, 최선 모두 O(n log n)으로 매우 효율적이며, 추가적인 메모리 사용이 적습니다. 그러나 힙 정렬은 데이터의 상대적인 위치를 바꿀 수 있기 때문에 안정적인 정렬은 아닙니다.

Java로 힙 정렬 구현

아래 예제는 Java로 최대 힙을 사용한 힙 정렬을 구현한 것입니다.

public class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;

        // 최대 힙 구축
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // 요소를 하나씩 힙에서 추출
        for (int i = n - 1; i > 0; i--) {
            // 현재 루트(가장 큰 값)를 끝으로 이동
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 감소된 힙에서 루트 재정렬
            heapify(arr, i, 0);
        }
    }

    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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 재귀적으로 힙을 정렬
            heapify(arr, n, largest);
        }
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        HeapSort heapSort = new HeapSort();
        heapSort.sort(arr);

        System.out.println("정렬된 배열: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

위 코드는 최대 힙을 생성한 후, 가장 큰 요소를 반복적으로 제거하여 배열을 정렬합니다.

C로 힙 정렬 구현

다음은 C 언어로 힙 정렬을 구현한 예제입니다.

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("정렬된 배열: \n");
    printArray(arr, n);
    return 0;
}

위 C 코드 역시 최대 힙을 구축하고, 가장 큰 요소를 반복적으로 제거하여 정렬을 수행합니다. heapify 함수는 재귀적으로 호출되어 힙 속성을 유지하도록 합니다.

힙 정렬의 특징

• 시간 복잡도: 힙 정렬의 시간 복잡도는 O(n log n)입니다. 이는 힙을 만드는 데 O(n log n)의 시간이 소요되고, 요소를 제거하고 재정렬하는 데도 O(n log n)의 시간이 소요되기 때문입니다.
• 공간 복잡도: 힙 정렬은 추가적인 배열을 사용하지 않기 때문에 공간 복잡도가 O(1)입니다. 이는 제자리(in-place) 정렬 알고리즘이라는 것을 의미합니다.
• 안정성: 힙 정렬은 안정적인 정렬 알고리즘이 아닙니다. 데이터의 상대적인 위치가 변경될 수 있기 때문입니다.

결론

힙 정렬은 최악의 경우에도 O(n log n)의 시간 복잡도를 가지는 효율적인 정렬 알고리즘입니다. 추가적인 메모리 사용이 적어 메모리 효율성도 좋습니다. 그러나 힙 정렬은 데이터의 상대적인 순서가 보장되지 않기 때문에 안정적인 정렬을 요구하는 상황에서는 다른 알고리즘을 고려해야 합니다.

Java와 C로 구현된 예제를 통해 힙 정렬의 동작 원리를 이해하고 직접 구현해 보세요. 힙 자료구조와 힙 정렬은 알고리즘 문제를 해결하는 데 매우 유용하며, 특히 우선순위 큐와 같은 문제에서 중요한 역할을 합니다.