2026-02-03 | 6 min read | 120 | 정렬 힙 정렬 알고리즘 힙

3-6. 정렬 알고리즘: 힙 정렬 (심화)

1. 힙 정렬의 이해: 효율적인 정렬의 세계로

힙 정렬(Heap Sort)은 정렬 알고리즘 중에서도 특히 효율성 면에서 뛰어난 성능을 보이는 알고리즘입니다. 힙 자료구조를 기반으로 하며, 평균 및 최악의 경우 모두 $O(n \log n)$의 시간 복잡도를 보입니다. 이는 병합 정렬(Merge Sort) 및 퀵 정렬(Quick Sort)과 동등한 수준으로, 대규모 데이터셋을 정렬할 때 매우 유용합니다. 힙 정렬의 핵심 아이디어는 주어진 데이터를 힙 구조로 만들고, 힙의 특성을 이용하여 정렬하는 것입니다.

1) 정렬 알고리즘의 중요성

정렬 알고리즘은 컴퓨터 과학의 가장 기본적인 알고리즘 중 하나이며, 데이터 처리의 효율성을 크게 향상시킵니다. 정렬된 데이터는 탐색, 병합, 검색 등 다양한 연산에서 훨씬 더 빠르게 처리될 수 있습니다. 예를 들어, 이진 탐색은 정렬된 데이터에서만 효과적으로 작동하며, 데이터베이스 시스템, 검색 엔진, 운영 체제 등 다양한 분야에서 핵심적인 역할을 수행합니다.

2) 힙 정렬의 배경

힙 정렬은 힙 자료구조의 특성을 활용하여 정렬 문제를 해결합니다. 힙은 완전 이진 트리(Complete Binary Tree) 형태를 가지며, 부모 노드는 자식 노드보다 크거나 같은(최대 힙, Max Heap) 또는 작거나 같은(최소 힙, Min Heap) 값을 갖는다는 속성을 가집니다. 이러한 힙의 특성을 이용하여, 가장 큰(또는 작은) 값을 빠르게 찾아낼 수 있으며, 이를 반복적으로 수행하여 전체 데이터를 정렬할 수 있습니다. 힙 정렬은 1964년 J. W. J. Williams에 의해 처음 제안되었습니다.

2. 힙 자료구조와 힙 정렬의 연결

힙 정렬을 이해하기 위해서는 힙 자료구조에 대한 이해가 필수적입니다. 힙은 우선순위 큐(Priority Queue)를 구현하는 데 주로 사용되며, 다음과 같은 연산을 지원합니다.

insert(key): 새로운 key 값을 힙에 삽입합니다.
extractMax() (최대 힙의 경우) 또는 extractMin() (최소 힙의 경우): 힙에서 가장 큰(또는 작은) 값을 제거하고 반환합니다.
getMax() (최대 힙의 경우) 또는 getMin() (최소 힙의 경우): 힙에서 가장 큰(또는 작은) 값을 반환하지만 제거하지는 않습니다.

힙 정렬은 이 중 extractMax() (또는 extractMin()) 연산을 반복적으로 사용하여 데이터를 정렬합니다.

1) 힙의 구조

힙은 완전 이진 트리 구조를 가지므로, 배열을 이용하여 효율적으로 구현할 수 있습니다. 배열의 인덱스를 이용하여 부모 노드와 자식 노드의 위치를 계산할 수 있습니다.

부모 노드의 인덱스: parent(i) = floor((i - 1) / 2)
왼쪽 자식 노드의 인덱스: left(i) = 2i + 1
오른쪽 자식 노드의 인덱스: right(i) = 2i + 2

힙 구조와 배열 표현 설명 뒤

2) 힙의 연산: `heapify`

힙 정렬의 핵심 연산 중 하나는 heapify입니다. heapify는 특정 노드를 기준으로 해당 노드와 자식 노드 간의 힙 속성을 만족하도록 힙 구조를 재구성하는 연산입니다. 최대 힙의 경우, 부모 노드가 자식 노드보다 작을 경우, 두 노드의 값을 교환하여 힙 속성을 유지합니다. 이러한 과정을 루트 노드에서 시작하여 하위 노드로 반복적으로 수행합니다.

3) 최대 힙과 최소 힙

힙에는 최대 힙과 최소 힙 두 가지 종류가 있습니다.

최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같은 힙. (Max Heap)
최소 힙: 부모 노드의 값이 자식 노드의 값보다 작거나 같은 힙. (Min Heap)

힙 정렬은 최대 힙 또는 최소 힙 모두 사용할 수 있지만, 구현 방식에 약간의 차이가 있습니다. 일반적으로 최대 힙을 사용하여 오름차순으로 정렬하며, 최소 힙을 사용하여 내림차순으로 정렬합니다.

3. 힙 정렬 알고리즘의 동작 원리

힙 정렬은 다음 두 단계로 구성됩니다.

힙 구성(Heapify): 정렬할 데이터를 힙 자료구조로 만듭니다.
정렬(Sort): 힙의 루트 노드(최대값 또는 최소값)를 마지막 노드와 교환하고, 힙의 크기를 하나 줄인 후, 남은 힙을 다시 힙 구조로 만듭니다. 이 과정을 반복합니다.

1) 힙 구성 단계

힙 구성 단계는 주어진 데이터를 힙의 형태로 변환하는 과정입니다. 배열의 모든 요소를 힙에 삽입하는 방식으로 구현할 수도 있지만, 일반적으로는 "바텀업(bottom-up)" 방식을 사용합니다. 바텀업 방식은 배열의 마지막 노드부터 시작하여, 각 노드에 대해 heapify 연산을 수행하여 힙 속성을 만족하도록 힙을 구성합니다.

2) 정렬 단계

정렬 단계에서는 힙의 루트 노드(가장 큰 값)를 배열의 마지막 요소와 교환합니다. 이 교환은 정렬된 부분을 힙의 마지막 부분에 위치시키고, 정렬되지 않은 부분의 크기를 줄이는 효과를 가져옵니다. 이후, 루트 노드를 제외한 나머지 부분에 대해 heapify 연산을 수행하여 힙 속성을 다시 만족시킵니다. 이 과정을 힙의 크기가 1이 될 때까지 반복합니다.

힙 정렬 알고리즘의 동작 원리 설명 뒤

4. 힙 정렬의 시간 복잡도 분석

힙 정렬의 시간 복잡도는 다음과 같습니다.

힙 구성 단계: $O(n)$
정렬 단계: $O(n \log n)$ (각 노드를 제거하고 힙을 재구성하는 데 $\log n$ 시간이 소요되며, 이를 $n$번 반복)

따라서, 힙 정렬의 전체 시간 복잡도는 $O(n \log n)$입니다.

1) 힙 구성 단계의 시간 복잡도

힙 구성 단계의 시간 복잡도는 $O(n)$입니다. 이는 각 노드에 대해 heapify 연산을 수행하지만, 모든 노드를 거치는 것이 아니라, 힙의 깊이에 따라 연산 횟수가 달라지기 때문입니다.

2) 정렬 단계의 시간 복잡도

정렬 단계의 시간 복잡도는 $O(n \log n)$입니다. 힙에서 최대(또는 최소) 값을 추출하고 힙을 재구성하는 데 $\log n$ 시간이 소요됩니다. 이를 $n$번 반복하므로, 전체 시간 복잡도는 $n \times \log n = O(n \log n)$이 됩니다.

3) 공간 복잡도

힙 정렬은 제자리 정렬(in-place sort) 알고리즘입니다. 즉, 입력 배열 외에 별도의 추가 공간을 거의 사용하지 않습니다. 따라서 공간 복잡도는 $O(1)$입니다.

5. 힙 정렬의 구현 (파이썬 예시)

def heapify(arr, n, i):
    """
    주어진 노드 i를 루트로 하는 서브트리를 힙 속성을 만족하도록 재구성합니다.
    """
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)

def heap_sort(arr):
    """
    힙 정렬 알고리즘을 구현합니다.
    """
    n = len(arr)

    # 1. 힙 구성 (Build Max-Heap)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2. 정렬
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap
        heapify(arr, i, 0)

# 예시
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("정렬된 배열:", arr)

1) `heapify` 함수

heapify 함수는 주어진 노드 i를 루트로 하는 서브트리가 힙 속성을 만족하도록 재귀적으로 힙을 재구성합니다. 자식 노드 중 더 큰 값을 가진 노드와 현재 노드를 비교하여, 힙 속성을 위반하는 경우 두 노드의 값을 교환하고, 교환된 자식 노드를 기준으로 다시 heapify를 호출합니다.

2) `heap_sort` 함수

heap_sort 함수는 힙 정렬 알고리즘을 구현합니다.

힙 구성: 주어진 배열을 힙으로 만들기 위해, 배열의 중간 노드부터 시작하여 루트 노드까지 heapify를 호출합니다.
정렬: 힙의 루트 노드(가장 큰 값)를 배열의 마지막 요소와 교환하고, 힙의 크기를 하나 줄인 후, 루트 노드에 대해 heapify를 호출하여 힙 속성을 유지합니다. 이 과정을 배열의 크기가 1이 될 때까지 반복합니다.

6. 힙 정렬의 장단점과 활용

1) 장점

시간 복잡도: $O(n \log n)$으로, 병합 정렬 및 퀵 정렬과 유사한 뛰어난 성능을 보입니다.
제자리 정렬: 추가적인 메모리 공간을 거의 사용하지 않아 메모리 사용량이 효율적입니다.
최악의 경우에도 $O(n \log n)$ 보장: 퀵 정렬과 달리 최악의 경우에도 성능 저하가 없습니다.

2) 단점

퀵 정렬보다 느림: 실제 구현에서 퀵 정렬에 비해 약간의 성능 저하가 있을 수 있습니다. (상수 인자 차이)
불안정 정렬: 동일한 값을 가진 요소들의 상대적인 순서가 보존되지 않을 수 있습니다.

3) 활용 사례

힙 정렬은 다음과 같은 경우에 유용하게 사용될 수 있습니다.

대규모 데이터셋의 정렬
메모리 공간 제약이 있는 환경
최악의 경우에도 일정한 성능을 보장해야 하는 경우
우선순위 큐 구현

7. 힙 정렬 시 주의사항 및 개선 방법

1) 힙 구성 단계의 최적화

힙 구성 단계에서 바텀업 방식을 사용하면, 모든 노드를 처음부터 힙에 삽입하는 방식보다 효율적으로 힙을 구성할 수 있습니다. 바텀업 방식은 힙의 깊이가 깊어질수록 적은 횟수의 비교 연산으로 힙을 구성할 수 있기 때문입니다.

2) 퀵 정렬과의 비교

퀵 정렬은 평균적으로 힙 정렬보다 빠르지만, 최악의 경우 $O(n^2)$의 시간 복잡도를 가질 수 있습니다. 힙 정렬은 최악의 경우에도 $O(n \log n)$을 보장하므로, 데이터의 특성을 알 수 없는 경우 힙 정렬을 사용하는 것이 안전합니다.

3) 안정 정렬 여부

힙 정렬은 불안정 정렬 알고리즘입니다. 즉, 동일한 값을 가진 요소들의 상대적인 순서가 보존되지 않을 수 있습니다. 안정 정렬을 필요로 하는 경우에는 다른 정렬 알고리즘(예: 병합 정렬)을 사용하는 것이 좋습니다.

8. 결론

힙 정렬은 $O(n \log n)$의 시간 복잡도와 $O(1)$의 공간 복잡도를 가진 효율적인 정렬 알고리즘입니다. 힙 자료구조의 특성을 활용하여 대규모 데이터셋을 정렬하는 데 유용하며, 최악의 경우에도 일정한 성능을 보장합니다. 힙 정렬의 원리를 이해하고, 실제 구현을 통해 힙 정렬의 장점을 경험해 보시기 바랍니다.