힙 정렬 (Heap Sort) 완벽 가이드

자료구조 ‘힙(Heap)‘의 강력한 특성을 그대로 이용한 정렬 알고리즘, **힙 정렬(Heap Sort)**에 대해 알아보겠습니다.

1. 힙 정렬이란?

힙 정렬은 최대 힙(Max Heap)이나 최소 힙(Min Heap) 트리를 구성하여 데이터를 정렬하는 방식입니다.

오름차순 정렬을 위해서는 **최대 힙(Max Heap)**을 사용합니다. 최대 힙의 특성상 루트 노드가 항상 가장 큰 값을 가지므로, 이 루트 노드를 하나씩 꺼내어 배열의 뒤쪽부터 채워 넣으면 정렬이 완성됩니다.

2. 동작 과정 (오름차순 기준)

최대 힙 만들기 (Heapify): 정렬되지 않은 1차원 배열을 최대 힙 구조로 만듭니다. (부모가 자식보다 항상 크거나 같음)
루트 노드 추출 및 교환:
- 최대 힙의 루트 노드(현재 배열에서 가장 큰 값, arr[0])를 배열의 맨 마지막 원소와 자리 바꿈(Swap)합니다.
- 이제 가장 큰 값은 배열의 끝으로 이동하여 정렬이 확정되었습니다.
힙 재구성 (Heapify Down):
- 방금 교환된 맨 마지막 원소(정렬 확정된 원소)를 제외한 나머지 배열에 대해, 새로운 루트 노드가 힙 성질을 만족하도록 자식 노드들과 비교하며 아래로 내립니다.
이 과정을 배열의 모든 원소가 정렬될 때까지(배열 크기가 1이 될 때까지) 반복합니다.

3. 파이썬(Python) 구현 예시

힙을 직접 배열로 구현하여 정렬하는 정석 코드입니다.

def heapify(arr, n, i):
    """
    루트 노드 인덱스 i를 기준으로 최대 힙 성질을 맞추는 함수 (Sift-Down)
    n: 힙의 크기 (정렬 대상 범위)
    """
    largest = i          # 루트 노드를 가장 크다고 가정
    left = 2 * i + 1     # 왼쪽 자식 인덱스
    right = 2 * i + 2    # 오른쪽 자식 인덱스
 
    # 왼쪽 자식이 존재하고, 부모(largest)보다 크다면 largest 갱신
    if left < n and arr[left] > arr[largest]:
        largest = left
 
    # 오른쪽 자식이 존재하고, 현재 largest보다 크다면 largest 갱신
    if right < n and arr[right] > arr[largest]:
        largest = right
 
    # largest가 루트(i)가 아니라면 자식과 위치 교환
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 교환된 자식 위치에서 다시 heapify 재귀 호출
        heapify(arr, n, largest)
 
def heap_sort(arr):
    n = len(arr)
 
    # 1. 초기 최대 힙 구성 (Build Max Heap)
    # 마지막 리프 노드의 부모 노드들부터 루트 노드(0)까지 역순으로 heapify 적용
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
 
    # 2. 요소를 하나씩 추출하여 정렬
    for i in range(n - 1, 0, -1):
        # 현재 루트(가장 큰 값)를 배열의 맨 끝 요소(i)와 교환
        arr[0], arr[i] = arr[i], arr[0]
        # 힙 사이즈를 1 줄이고(루트 제외) 변경된 루트에 대해 다시 heapify 적용
        heapify(arr, i, 0)
 
    return arr
 
# 사용 예시
data = [12, 11, 13, 5, 6, 7]
print("정렬 전:", data)
print("정렬 후:", heap_sort(data))

참고: 파이썬의 내장 모듈 heapq를 사용하면 아주 쉽게 구현할 수 있지만, 인터뷰에서는 위처럼 heapify 로직을 직접 구현할 수 있는지를 묻는 경우가 많습니다.

4. 시간 복잡도 및 공간 복잡도

시간 복잡도:
- 최악, 최선, 평균 모두 $O (N lo g N)$ 입니다.
- 초기 힙을 구성하는 데 $O (N)$ , 요소를 하나 추출하고 힙을 재구성(Heapify)하는 데 $O (lo g N)$ 이 걸리며 이를 $N$ 번 반복하므로 총 $O (N lo g N)$ 입니다.
공간 복잡도: $O (1)$
- 별도의 배열 없이 기존 배열 내에서 노드 간의 교환만으로 힙 구조를 유지하며 정렬하므로 제자리 정렬(In-place Sort)입니다.

5. 특징

장점:
- 항상 $O (N lo g N)$ 의 시간 복잡도를 보장하여 최악의 경우에도 빠릅니다.
- 추가적인 메모리 공간이 필요하지 않은 제자리 정렬(In-place)입니다. (병합 정렬의 단점 극복)
- 가장 큰(또는 작은) $K$ 개의 원소만 필요할 때 전체를 정렬할 필요 없이 $K$ 번만 추출하면 되므로 매우 효율적입니다.
단점:
- **불안정 정렬(Unstable Sort)**입니다.
- 실제 속도 측면에서는 배열의 인덱스를 건너뛰면서 접근(예: 2*i+1)하기 때문에 캐시 지역성(Cache Locality)이 떨어져 퀵 정렬(Quick Sort)보다 느린 편입니다.

요약

힙 정렬은 이진 트리 기반의 최대 힙 구조를 사용하여 항상 $O (N lo g N)$ 성능을 내는 추가 메모리가 필요 없는 정렬입니다. 퀵 정렬의 최악의 경우( $O (N^{2})$ )와 병합 정렬의 추가 공간 필요( $O (N)$ )라는 단점을 모두 해결한 이론적으로 완벽에 가까운 정렬입니다. Heapify 과정을 코드로 직접 짤 수 있도록 연습하는 것이 중요합니다.

anonymous.rs

Explorer

정렬 알고리즘: 힙 정렬 (Heap Sort)