Heap Sort

핵심 아이디어

힙 정렬은 우선순위 큐에서 원소를 하나씩 꺼내면 자동으로 정렬된다는 관찰에서 출발한다. 오름차순 결과를 원한다면 최대 힙²을 만든 뒤 루트를 $n$번 반복 추출하면 된다. 추출된 값을 매번 배열의 "사용하지 않는 꼬리"에 쌓아 두면 별도의 출력 버퍼 없이 같은 배열에서 정렬이 끝난다.

즉, 힙 정렬은 다음 두 단계로 구성된다.

1. 힙 구성(BUILD-MAX-HEAP): 입력 배열 $A[1..n]$을 최대 힙 속성을 만족하도록 재배치한다.
2. 반복 추출(HEAPSORT): 루트 $A[1]$과 마지막 원소 $A[\text{heap-size}]$을 교환하여 현재 최댓값을 정렬된 영역으로 밀어내고, 힙 크기를 1 줄인 뒤 $A[1]$에서 sift-down을 수행한다. 힙 크기가 1이 될 때까지 반복한다.

힙의 배열 표현, 부모·자식 인덱스 공식, sift-up·sift-down의 기본 메커니즘은 힙에 대한 포스트를 참고하자. 이 글에서는 정렬에 특화된 관점에서만 설명한다.

알고리즘

MAX-HEAPIFY

부분 트리의 루트 $i$가 최대 힙 속성을 위반할 때, $i$를 올바른 위치까지 아래로 내려 보내 속성을 복원한다. 두 자식 중 더 큰 쪽과 비교하여, 자식이 더 크면 교환하고 그 자식을 새 $i$로 삼아 재귀한다.

def max_heapify(A, i, heap_size):
    left, right = 2 * i, 2 * i + 1
    largest = i
    if left <= heap_size and A[left] > A[largest]:
        largest = left
    if right <= heap_size and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest, heap_size)

현재 노드에서 리프까지 내려가므로 시간 복잡도는 트리 높이에 비례한 $O(\log n)$이다.

BUILD-MAX-HEAP

배열의 뒷쪽 절반($i = \lfloor n/2 \rfloor + 1, \dots, n$)은 모두 리프이므로 이미 힙 속성을 자명하게 만족한다. 따라서 $i = \lfloor n/2 \rfloor$부터 1까지 역순으로 MAX-HEAPIFY를 호출하면 된다. 역순 호출이 본질적인 이유는, 호출 시점에 $i$의 두 자식을 루트로 하는 부분 트리가 이미 최대 힙이어야 MAX-HEAPIFY가 유효하기 때문이다.

def build_max_heap(A):
    n = len(A) - 1                  # 1-based 인덱스
    for i in range(n // 2, 0, -1):
        max_heapify(A, i, n)

전체 비용은 $O(n)$이다³. "각 호출이 $O(\log n)$, 호출이 $n/2$번이므로 $O(n \log n)$"이라는 분석은 느슨한 상계일 뿐이며, 실제로는 층별 노드 수가 지수적으로 감소하는 효과가 결합해 선형으로 수렴한다.

HEAPSORT

def heapsort(A):
    build_max_heap(A)
    heap_size = len(A) - 1
    for i in range(heap_size, 1, -1):
        A[1], A[i] = A[i], A[1]       # 현재 최댓값을 정렬된 꼬리로
        heap_size -= 1
        max_heapify(A, 1, heap_size)

한 번의 교환으로 현재 최댓값이 배열의 꼬리에 고정된다. 힙 크기를 줄이면 그 위치는 더 이상 힙에 포함되지 않으며, MAX-HEAPIFY는 줄어든 힙에 대해서만 속성을 복원한다. 이 사이클을 $n - 1$번 반복하면 배열 전체가 오름차순으로 정렬된다.

동작 과정

입력 $A = [5, 3, 8, 1, 9, 7]$을 예로 들자. 먼저 BUILD-MAX-HEAP이 $A$를 $[9, 5, 8, 1, 3, 7]$로 재배치한다. 그 뒤 반복 추출 루프의 한 사이클이 어떻게 진행되는지 살펴본다.

이 사이클이 끝나면 $A = [8, 5, 7, 1, 3, 9]$가 되고, 뒷쪽 한 칸이 "정렬된 영역"으로 확정된다. 같은 사이클을 반복할 때마다 정렬된 영역이 왼쪽으로 한 칸씩 자라면서 힙은 한 칸씩 줄어들고, 결국 $A = [1, 3, 5, 7, 8, 9]$로 마감된다.

정확성 증명

두 개의 루프 불변식으로 알고리즘의 정확성을 보인다. 각 불변식은 초기화 · 유지 · 종료의 3단 구조로 검증한다.

• BUILD-MAX-HEAP: 루프 변수 $i$가 $\lfloor n/2 \rfloor$에서 1까지 감소할 때, 각 반복의 시작 시점에서 노드 $i+1, i+2, \dots, n$은 모두 어떤 최대 힙의 루트이다.
  • 초기화: $i = \lfloor n/2 \rfloor$일 때, 인덱스 $i+1, \dots, n$은 모두 리프이므로 자명하게 크기 1의 최대 힙이다.
  • 유지: $i$의 두 자식($2i$, $2i+1$)은 가정에 의해 이미 최대 힙의 루트이다. 이 전제에서 MAX-HEAPIFY(A, i, n)은 노드 $i$를 루트로 하는 부분 트리를 최대 힙으로 만든다. 따라서 다음 반복 시작 시점에 $i, i+1, \dots, n$이 모두 최대 힙의 루트이다.
  • 종료: $i = 0$으로 종료되는 시점에 노드 $1, 2, \dots, n$이 모두 최대 힙의 루트이므로, 특히 $A[1..n]$ 전체가 최대 힙이다.
• HEAPSORT: 외부 루프가 $i = n, n-1, \dots, 2$로 감소할 때, 각 반복 시작 시점에 다음이 성립한다. (i) $A[1..i]$는 최대 힙이다. (ii) $A[i+1..n]$은 오름차순으로 정렬되어 있으며, 그 안의 모든 원소는 $A[1..i]$의 모든 원소보다 크거나 같다.
  • 초기화: 루프 시작 직전 BUILD-MAX-HEAP으로 $A[1..n]$이 최대 힙이고, $A[n+1..n]$은 비어 있으므로 자명하다.
  • 유지: $A[1]$이 $A[1..i]$의 최댓값이므로 $A[1]$과 $A[i]$를 교환해도 (ii)의 정렬·크기 조건은 깨지지 않는다. 그 뒤 힙 크기를 $i - 1$로 줄이고 MAX-HEAPIFY(A, 1, i-1)을 호출하면 $A[1..i-1]$이 다시 최대 힙이 되어 (i)가 복원된다.
  • 종료: $i = 1$일 때 $A[2..n]$이 오름차순이고 $A[1]$은 그 어떤 원소보다도 작거나 같으므로 $A[1..n]$ 전체가 오름차순이다.

두 불변식이 각각 성립하므로 힙 정렬은 임의 입력에 대해 오름차순 결과를 반환한다.

시간 복잡도

힙 구성이 $O(n)$인 본질은 높이 $h$에 있는 노드 수가 최대 $\lceil n/2^{h+1}\rceil$이고 각 노드의 sift-down 비용이 $O(h)$라는 사실에서 비롯된다. 두 값을 곱해 모든 높이에 대해 합하면

$\sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h) \;=\; O\!\left( n \sum_{h=0}^{\infty} \frac{h}{2^h} \right) \;=\; O(n)$

이 된다($\sum_{h=0}^{\infty} h/2^h = 2$로 수렴한다). 그러나 이 $O(n)$은 뒤따르는 추출 루프의 $O(n \log n)$에 흡수되므로, 알고리즘 전체의 점근 복잡도는 $O(n \log n)$이다.

힙 정렬은 최악·평균·최선 모두 $\Theta(n \log n)$이다. 입력이 이미 정렬된 상태라 해도 힙 구성은 항상 수행되고, 추출 루프의 모든 MAX-HEAPIFY 호출이 적어도 한 레벨은 내려가야 한다. 이는 최선이 $O(n)$이 될 수 있는 삽입 정렬이나 최적화된 버블 정렬과 대조된다.

다른 정렬과의 비교

힙 정렬의 구조적 강점은 아무리 최악이어도 $O(n \log n)$이 보장된다는 점과 $O(1)$ 보조 공간을 동시에 제공한다는 점이다. 병합 정렬은 최악 $O(n \log n)$을 달성하지만 $O(n)$의 추가 메모리가 필요하고, 퀵 정렬은 평균 성능이 뛰어나지만 최악이 $O(n^2)$까지 떨어질 수 있다. 최악 지연이 중요한 실시간 시스템이나 메모리가 제한된 임베디드 환경에서 힙 정렬이 선호되는 이유다.

다만 실무 벤치마크에서 힙 정렬은 잘 튜닝된 퀵 정렬보다 느린 경우가 많다. 힙 정렬의 sift-down 경로는 인덱스 $i \to 2i \to 4i \to \dots$로 지수적 점프를 하므로, 단계마다 멀리 떨어진 캐시 라인을 건드려 캐시 지역성⁵이 나쁘다. 이런 이유로 C++ STL의 std::sort는 인트로정렬을 채택하여 평상시에는 퀵 정렬로 빠르게 처리하고, 재귀 깊이가 $2\lfloor\log_2 n\rfloor$를 넘으면 힙 정렬로 전환해 최악 $O(n \log n)$을 보장한다. 즉 힙 정렬은 하이브리드 정렬의 안전망으로서 현대 표준 라이브러리에 스며들어 있다.

Python 구현

def heapsort(A):
    """1-based 인덱스 배열 A[1..n]을 제자리에서 오름차순 정렬."""
    n = len(A) - 1  # A[0]은 사용하지 않음

    def max_heapify(i, heap_size):
        while 2 * i <= heap_size:
            child = 2 * i
            if child + 1 <= heap_size and A[child + 1] > A[child]:
                child += 1
            if A[i] >= A[child]:
                break
            A[i], A[child] = A[child], A[i]
            i = child

    # 1. 힙 구성 — O(n)
    for i in range(n // 2, 0, -1):
        max_heapify(i, n)

    # 2. 반복 추출 — O(n log n)
    for i in range(n, 1, -1):
        A[1], A[i] = A[i], A[1]
        max_heapify(1, i - 1)

표준 라이브러리의 heapq를 쓰면 더 짧지만, 원소를 하나씩 heappop하여 새 리스트에 담으므로 이 버전은 엄밀히 제자리 정렬이 아니다.

import heapq

def heapsort_stdlib(data):
    heapq.heapify(data)
    return [heapq.heappop(data) for _ in range(len(data))]

어디에 쓰이는가

힙 정렬은 지연 시간이 일정 수준을 넘지 않도록 보장되어야 하는 환경에서 특히 가치가 있다. 실시간 시스템에서 최대 응답 시간을 계산해야 할 때, 메모리가 제한적이어서 $O(n)$ 보조 공간을 허용할 수 없을 때가 대표적이다. 또한 인트로정렬처럼 하이브리드 정렬의 최악 대비 안전망 역할로도 자주 쓰인다.

원소 $n$개 중 상위 $k$개만 필요한 경우에는 전체 정렬 대신 부분 힙 정렬(heapq.nlargest)을 쓰면 $O(n + k \log n)$에 끝낼 수 있다. 힙을 "정렬 기계"가 아닌 "선택 기계"로 다시 보는 관점이며, $k \ll n$일 때 힙 정렬 전체를 돌리는 것보다 훨씬 빠르다.

---

출처

• Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press, Chapter 6.
• Sedgewick, R. and Wayne, K. (2011) Algorithms. 4th edn. Upper Saddle River, NJ: Addison-Wesley, Section 2.4.
• Musser, D. R. (1997) 'Introspective Sorting and Selection Algorithms', Software: Practice and Experience, 27(8), pp. 983–993.
• Python Software Foundation (2025) heapq — Heap queue algorithm. Available at: https://docs.python.org/3/library/heapq.html.

Footnotes

1. 제자리 정렬in-place sort은 입력 배열 외에 입력 크기에 비례하지 않는 상수 수준의 보조 공간만 사용하는 정렬이다. 힙 정렬은 스왑 변수와 인덱스 몇 개만으로 동작하여 $O(1)$ 공간을 만족한다. ↩

2. 최대 힙max-heap은 모든 노드 $i$에 대해 $A[\text{parent}(i)] \ge A[i]$가 성립하는 힙으로, 루트가 항상 집합의 최댓값이다. 자세한 정의와 배열 표현은 Heap 참고. ↩

3. BUILD-MAX-HEAP의 $O(n)$ 증명은 Heap 포스트의 build-heap 풋노트에 상세히 기술되어 있다. 요지는 높이 $h$에 있는 노드 수 $\lceil n/2^{h+1}\rceil$과 sift-down 비용 $O(h)$의 곱을 합하면 $\sum_{h=0}^{\infty} h/2^h = 2$로 수렴해 전체가 $O(n)$이 된다는 것이다. ↩

4. 안정 정렬stable sort은 같은 키를 가진 원소들의 입력 순서가 정렬 후에도 보존되는 성질을 뜻한다. 힙 정렬은 sift-down 과정에서 동일 키의 상대 위치가 뒤섞일 수 있어 불안정하다. ↩

5. 캐시 지역성cache locality이란 프로그램이 최근 접근한 메모리 근처를 다시 접근하는 경향이다. 힙 정렬의 sift-down은 $i \to 2i \to 4i \to \dots$로 지수적 점프를 하므로 매 단계가 다른 캐시 라인을 건드려, 이웃 원소를 순차 접근하는 퀵/병합 정렬에 비해 캐시 미스가 많다. ↩