힙 정렬 (Heap Sort)

구현 코드 예시

def heapify(arr, n, i):
    """i를 루트로 하는 서브트리를 최대 힙으로 고친다. 자식 서브트리는 이미 힙이라고 가정."""
    largest = i
    left, right = 2 * i + 1, 2 * i + 2

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

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)          # 내려간 자리에서 다시 확인


def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):   # 마지막 부모부터 거꾸로 올라오며 힙 구성
        heapify(arr, n, i)

    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # 최댓값을 뒤로 확정
        heapify(arr, end, 0)                  # 남은 앞부분만 다시 힙으로
    return arr

힙 구성 루프가 n // 2 - 1에서 시작하는 이유는 그 뒤가 전부 리프이기 때문이다. 리프는 자식이 없으니 이미 힙 조건을 만족한다. 그리고 거꾸로 올라와야 하는 이유는 sift-down이 "자식 서브트리는 이미 힙"이라는 전제 위에서 동작하기 때문이다. 위에서부터 내려가면 이 전제가 깨진다.

실전에서는 우선순위 큐로 쓴다

파이썬 heapq는 최소 힙만 제공한다. 최대 힙이 필요하면 값에 마이너스를 붙여 넣고 꺼낼 때 다시 뒤집는 것이 관용적인 방법이다.

import heapq

# 최소 힙
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
smallest = heapq.heappop(pq)      # 1

# 최대 힙 흉내
maxpq = []
heapq.heappush(maxpq, -5)
heapq.heappush(maxpq, -1)
largest = -heapq.heappop(maxpq)   # 5

# 튜플을 넣으면 첫 원소 기준으로 정렬된다 — (비용, 노드) 형태가 다익스트라의 기본형
heapq.heappush(pq, (3, "B"))

# 이미 있는 리스트를 O(n)에 힙으로 만들기
nums = [5, 1, 9, 3]
heapq.heapify(nums)

자주 하는 실수

• 더 작은 자식과 교환한다. 최대 힙에서는 반드시 더 큰 자식과 바꿔야 한다. 작은 쪽과 바꾸면 올라간 값이 형제보다 작아 규칙이 또 깨진다.
• 자식 인덱스 범위를 확인하지 않는다. left < n, right < n 검사를 빼면 배열 밖을 읽는다. 정렬 단계에서 n이 계속 줄어들기 때문에 특히 위험하다.
• 힙을 위에서부터 만든다. range(0, n)으로 정방향 순회하면 sift-down의 전제가 깨져 힙이 제대로 만들어지지 않는다.
• 정렬 단계에서 n을 그대로 넘긴다. heapify(arr, end, 0)의 두 번째 인자는 줄어든 힙 크기여야 한다. n을 넘기면 이미 확정된 뒤쪽 값을 다시 힙에 끌어들인다.
• heapq가 최대 힙이라고 착각한다. 파이썬은 최소 힙이다. 부호 뒤집기를 잊으면 조용히 반대 결과가 나온다.

면접에서 이렇게 물어본다

• 힙이 만족해야 하는 두 조건은 무엇인가.
• 힙을 배열로 표현할 수 있는 이유와 부모·자식 인덱스 공식을 설명해 보라.
• 힙 만들기가 O(n log n)이 아니라 O(n)인 이유를 설명해 보라.
• 힙을 구성할 때 왜 마지막 부모부터 거꾸로 올라가야 하는가.
• 힙 정렬이 불안정 정렬인 이유는 무엇인가.
• 병합 정렬과 힙 정렬 모두 O(n log n)인데 실무에서 병합 정렬 계열이 더 많이 쓰이는 이유는 무엇인가.
• 우선순위 큐가 필요한 상황을 예로 들어 보라.