힙 정렬 알고리즘 원리, 코드, 시간 복잡도

쉬운 말로 설명하는 원리

힙 정렬은 최댓값을 더 빨리 찾는 선택 정렬입니다. 선택 정렬은 매번 정렬되지 않은 부분 전체를 훑어 O(n)이 듭니다. 힙 정렬은 정렬되지 않은 부분을 힙으로 유지하므로 최댓값이 항상 인덱스 0에 있고, 그것을 꺼낸 뒤 질서를 복구하는 비용은 O(log n)뿐입니다.

이진 힙은 포인터 없이 평범한 배열에 저장됩니다. 인덱스 i의 요소에 대해 다음이 성립합니다.

• 왼쪽 자식은 2*i + 1, 오른쪽 자식은 2*i + 2에 있습니다.
• 부모는 (i - 1) // 2에 있습니다.
• 최대 힙에서는 모든 부모가 자식보다 크거나 같으므로 가장 큰 요소가 인덱스 0에 있습니다.

1. 배열에서 최대 힙을 만듭니다. 마지막 비(非)리프 노드부터 인덱스 0까지 모든 비리프 노드를 sift down 합니다.
2. 루트(최댓값)를 힙의 마지막 요소와 교환합니다. 그 요소는 이제 최종 위치에 있습니다.
3. 힙을 한 칸 줄이고, 힙 성질이 다시 성립할 때까지 새 루트를 sift down 합니다.
4. 힙에 요소가 하나 남을 때까지 2단계와 3단계를 반복합니다.

단계별 예제

[4, 10, 3, 5, 1]을 정렬해 봅시다. 막대 뒤의 요소는 정렬이 끝나 확정된 것입니다.

파이썬 구현

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

파이썬의 heapq 모듈은 평범한 리스트 위에 최소 힙을 제공합니다. 모든 요소를 꺼내면 정렬된 리스트가 되는데, 이것이 짧은(제자리가 아닌) 힙 정렬입니다.

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

시간 복잡도와 공간 복잡도

힙을 상향식으로 만드는 것은 O(n log n)이 아니라 O(n)입니다. 완전 이진 트리에서 노드 높이의 합이 O(n)이기 때문입니다. 전체 비용은 추출 단계가 좌우합니다.

힙 정렬과 다른 정렬 비교

힙 정렬은 안정 정렬이 아닙니다. 루트를 끝으로 교환하면 같은 키를 가진 다른 요소를 지나쳐 버릴 수 있기 때문입니다. 주요 강점은 최악의 경우 O(n log n)이 보장되면서 추가 공간이 O(1)이라는 점으로, 이 조합은 퀵 정렬도 병합 정렬도 제공하지 못합니다. 약점은 메모리 접근입니다. 인덱스 i와 2*i + 1 사이를 오가며 점프하면 CPU 캐시를 제대로 활용하지 못하므로, 잘 구현된 퀵 정렬보다 보통 느립니다. Introsort는 퀵 정렬의 재귀가 너무 깊어질 때 대비책으로 힙 정렬을 사용합니다.

변형과 흔한 실수

• 부분 정렬: 가장 큰 k개 항목만 필요하면 힙을 만들고 k번 추출하며, O(n + k log n)입니다. 파이썬에서는 heapq.nlargest와 heapq.nsmallest가 이 일을 합니다.
• 스트림에서 상위 k개 찾기: 크기 k의 최소 힙을 유지하며 새 항목마다 넣거나 교체합니다. 시간 O(n log k), 메모리 O(k)입니다.
• 상향식 힙 정렬은 빈자리를 먼저 리프까지 내린 다음 위로 올려 비교 횟수를 줄입니다.
• Dijkstra가 만든 힙 기반 변형인 스무스 정렬(smoothsort)은 이미 정렬된 입력에서 O(n)이지만 복잡해서 거의 쓰이지 않습니다.

힙 정렬을 쓰는 경우

임베디드나 실시간 시스템처럼 추가 메모리 없이 최악의 경우 O(n log n)이 보장되어야 할 때, 또는 다른 정렬 내부의 안전망으로 힙 정렬을 쓰세요. 일상적인 파이썬 코드에서는 안정적이고 일반적인 데이터에서 더 빠른 sorted()를 쓰세요. 정렬보다 힙 자체가 더 유용합니다. 우선순위 큐, Dijkstra 최단 경로, 스케줄러, k개의 정렬된 리스트 병합(heapq.merge), 가장 큰 k개 값 찾기가 모두 힙을 기반으로 합니다. 면접에서는 힙 인덱스 공식, 힙 구성이 O(n)인 이유, 상위 k개 문제를 자주 묻습니다.