힙 정렬의 동작 원리와 선택 기준

루트의 극값을 꺼내며 배열을 정렬하는 방식

힙 정렬(Heap Sort)은 힙 자료구조를 바탕으로 하는 비교 정렬이다. 완전 이진 트리 형태의 최대 힙 또는 최소 힙을 만든 다음, 루트와 말단 원소를 교환하고 힙 속성을 다시 맞추는 과정을 반복한다.

오름차순 정렬에서는 최대 힙을 사용한다. 루트의 최댓값을 배열 끝으로 보낸 뒤 정렬 대상인 힙의 크기를 줄이고, 루트부터 sift-down을 수행한다. 이 과정을 반복하면 배열은 오름차순으로 정리된다.

힙은 모든 노드가 전역적으로 정렬된 구조는 아니다. 다만 최대 힙은 부모가 자식보다 크거나 같고, 최소 힙은 부모가 자식보다 작거나 같은 관계를 유지한다. 그 결과 루트에는 항상 극값이 위치한다.

힙을 만들고 복원하는 과정

배열을 최대 힙으로 바꾸는 Build-Heap은 하향식 sift-down 방식으로 수행하며 시간 복잡도는 O(n)이다. 이후 정렬 단계에서는 루트와 마지막 원소를 바꾸고 힙 크기를 1 줄인 뒤, 루트에서 힙 속성을 복원한다.

각 반복은 O(log n)이 걸리고, 이를 n−1회 수행해 전체 정렬을 완성한다. 오름차순에는 최대 힙, 내림차순에는 최소 힙을 사용하는 방식이 일반적이다.

⤢✕

비교 가능한 원소로 이뤄진 배열이 입력 조건이다. 비동질 타입을 비교하면 예외가 발생할 수 있으므로 비교 연산의 정의가 필요하다. 매우 큰 n에서 재귀형 heapify는 스택 초과 가능성이 있어 반복형 구현을 고려할 수 있다.

성능 보장과 제약

힙 정렬의 최악·평균·최선 시간 복잡도는 모두 O(n log n)이다. 추가 메모리는 O(1)만 사용하는 제자리 정렬이지만, 같은 키의 상대적 순서는 보장하지 않는 비안정 정렬이다.

배열 접근의 지역성이 낮아 캐시 친화성은 낮은 편이다. 반면 최악 시간의 예측 가능성이 필요한 경우에는 이 특성이 선택 근거가 될 수 있다.

Python 구현

Python 3.10+ 환경을 전제로 하며, 리스트의 모든 요소는 서로 비교 가능해야 한다.

# Python 3.10+
def heapify(a, n, i):
    # 반복형 sift-down (재귀 미사용)
    while True:
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and a[l] > a[largest]:
            largest = l
        if r < n and a[r] > a[largest]:
            largest = r
        if largest == i:
            break
        a[i], a[largest] = a[largest], a[i]
        i = largest

def build_max_heap(a):
    n = len(a)
    # 마지막 내부 노드부터 하향식 복원
    for i in range(n // 2 - 1, -1, -1):
        heapify(a, n, i)

def heapsort(a):
    n = len(a)
    build_max_heap(a)
    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heapify(a, i, 0)
    return a

if __name__ == "__main__":
    data = [9, 3, 1, 5, 4, 8, 2, 7, 6, 0]
    print(heapsort(data))

내림차순 정렬이 필요하면 최소 힙을 사용하거나 비교 부호를 반전할 수 있다. 안정성이 필요한 경우에는 (key, original_index) 튜플로 확장할 수 있지만, 추가 메모리 O(n)과 비교 비용 증가가 따른다.

다른 정렬 방식과의 차이

알고리즘	평균 시간	최악 시간	추가 메모리	안정성	캐시/운영 특성 요약
힙 정렬	O(n log n)	O(n log n)	O(1)	비안정	일정한 최악 보장, 캐시 비우호적
퀵 정렬	O(n log n)	O(n^2)	O(log n)	비안정	평균적 매우 빠름, 파티션 품질 민감
병합 정렬	O(n log n)	O(n log n)	O(n)	안정	외부정렬/대용량 스트리밍 유리
팀소트(Timsort)	O(n log n)	O(n log n)	O(n)	안정	실무 파이썬/자바 기본, 부분 정렬 데이터에 강함

메모리와 최악 성능이 제약인 경우

추가 메모리 O(1)이 필요한 내장 정렬 루틴의 대체 수단으로는 임베디드, 펌웨어, 커널 경로 등을 고려할 수 있다. 최악 성능 보장이 필요한 보안 또는 실시간 경로에도 맞는다.

외부 의존을 줄여야 하는 시스템 유틸리티에서는 단일 패스에서 예측 가능한 성능을 확보할 수 있고, 복잡한 파티셔닝 없이 구현할 수 있다. 데이터가 랜덤 분포이며 안정성이 필요 없는 배치 정렬 작업도 대상이 된다.

Top-K 추출이나 부분 정렬의 전처리에는 전체 힙 정렬 대신 크기 K의 힙을 유지할 수 있다. 이 경우 공간 O(K)로 상위 K를 추출하며, 로그 규모 업데이트로 스트리밍 데이터 처리를 다룬다.

최악 시간 O(n log n) 보장은 SLA 관점에서 지연 Tail 위험을 완화한다. 제자리 정렬의 추가 메모리 O(1)은 대용량 데이터의 메모리 압력을 줄이며, 힙 구성과 반복 추출로 이뤄진 일관된 로직은 표준 라이브러리 없이도 구현과 디버깅을 가능하게 한다.