힙 정렬의 활성 구간과 확정 구간

앞 글의 마지막 실행에서 최대 힙의 최댓값을 계속 꺼내면 큰 값부터 차례로 나왔습니다. 이것만으로도 정렬이 되지만, 꺼낸 값을 담을 리스트가 따로 필요합니다. 그런데 힙에서 값을 하나 꺼낼 때마다 힙의 길이가 하나씩 줄어 리스트 끝에 빈칸이 생깁니다. 꺼낸 최댓값을 바로 그 빈칸에 놓으면, 추가 리스트 없이 한 리스트 안에서 정렬을 끝낼 수 있습니다. 이것이 힙 정렬(heap sort)입니다. 이 글에서는 리스트를 힙으로 쓰는 앞부분과 정렬이 끝난 뒷부분으로 나누어 힙 정렬을 만들고, 이 정렬이 병합 정렬과 퀵 정렬에 비해 어떤 장단점이 있는지 비교합니다.

활성 구간과 확정 구간

힙 정렬은 리스트를 두 구간으로 나누어 생각합니다. 앞쪽 [0, end)는 아직 정렬되지 않은 값들을 최대 힙으로 유지하는 활성 구간이고, 뒤쪽 [end, n)은 최종 자리가 정해진 값들이 오름차순으로 놓인 확정 구간입니다. 처음에는 리스트 전체를 최대 힙으로 만들어 전체가 활성 구간이고, 확정 구간은 비어 있습니다.

한 단계에서는 활성 구간의 루트, 곧 남은 값 중 최댓값을 활성 구간의 마지막 칸과 맞바꿉니다. 그러면 최댓값이 마지막 칸에 놓이는데, 이 값은 확정 구간의 어떤 값보다도 크지 않고 활성 구간의 어떤 값보다도 작지 않으므로 그 칸이 최종 자리입니다. 이 칸을 활성 구간에서 빼서 확정 구간에 넣고, 루트로 올라온 값을 아래로 내리기로 제자리에 보내 활성 구간을 다시 최대 힙으로 만듭니다. 이 단계를 활성 구간에 값이 하나 남을 때까지 되풀이합니다.

[4, 1, 3, 2]를 정렬하는 과정은 다음과 같습니다.

활성 구간에 값이 하나만 남으면 그 값은 가장 작은 값이므로 따로 할 일이 없고, 리스트 전체가 [1, 2, 3, 4]로 정렬됩니다.

코드로 옮기기

sift_down은 앞 글의 것을 그대로 씁니다. 이 함수가 힙의 길이를 size로 따로 받았던 것은 바로 힙 정렬 때문입니다. 리스트의 길이는 그대로인 채로, 활성 구간의 길이 end만큼만 힙으로 다루어야 하기 때문입니다. 아래 heap_sort는 show=True로 부르면 단계마다 두 구간을 출력합니다.

def sift_down(values, root, size):
    while 2 * root + 1 < size:
        child = 2 * root + 1
        if child + 1 < size and values[child + 1] > values[child]:
            child += 1
        if values[root] >= values[child]:
            return
        values[root], values[child] = values[child], values[root]
        root = child


def heap_sort(values, show=False):
    result = list(values)
    n = len(result)
    for root in range(n // 2 - 1, -1, -1):
        sift_down(result, root, n)
    if show:
        print("힙 만들기", result)
    for end in range(n - 1, 0, -1):
        result[0], result[end] = result[end], result[0]
        sift_down(result, 0, end)
        if show:
            print("활성", result[:end], "확정", result[end:])
    return result


print(heap_sort([4, 1, 3, 2], show=True))
print(heap_sort([2, 2, 1]), heap_sort([]), heap_sort([5, 2, 4, 7, 1, 3]))

힙 만들기 [4, 2, 3, 1]
활성 [3, 2, 1] 확정 [4]
활성 [2, 1] 확정 [3, 4]
활성 [1] 확정 [2, 3, 4]
[1, 2, 3, 4]
[1, 2, 2] [] [1, 2, 3, 4, 5, 7]

두 번째 반복의 end는 n - 1부터 1까지 줄어듭니다. 각 단계에서 result[0]과 result[end]를 맞바꾸면 end 칸이 확정되고, 이어서 sift_down(result, 0, end)가 길이 end인 앞부분만 힙으로 고칩니다. 방금 확정한 end 칸은 길이 end의 바깥이라 다시 건드리지 않습니다. 빈 리스트나 원소가 하나인 리스트는 두 반복이 모두 한 번도 돌지 않고 그대로 돌아옵니다.

왜 맞고 왜 끝나는가

두 번째 반복이 시작될 때마다 다음 세 가지가 참입니다. 첫째, 활성 구간 result[0:end + 1]은 최대 힙입니다. 둘째, 확정 구간 result[end + 1:]에는 가장 큰 값들이 오름차순으로 들어 있습니다. 셋째, 활성 구간의 모든 값은 확정 구간의 어떤 값보다도 크지 않습니다. 처음에는 전체가 힙이고 확정 구간이 비어 있으므로 셋 다 성립합니다.

한 단계에서 루트와 end 칸을 맞바꾸면, 활성 구간의 최댓값이 end 칸으로 갑니다. 셋째 사실에 따라 이 값은 확정 구간의 값들보다 크지 않으므로, 확정 구간의 바로 앞에 붙여도 오름차순이 유지됩니다. 또 활성 구간에 남은 값들보다는 작지 않으므로 셋째 사실도 그대로입니다. 남은 활성 구간에서는 루트로 올라온 값만 힙 조건을 어길 수 있고 그 아래는 여전히 힙이므로, 루트에서 아래로 내리기를 한 번 하면 다시 최대 힙이 됩니다. 반복마다 활성 구간이 한 칸씩 줄어 n - 1단계 뒤에 끝나고, 그때는 확정 구간이 맨 앞의 한 칸을 뺀 전체이므로 리스트가 정렬되어 있습니다.

비용과 다른 정렬과의 비교

힙 만들기는 앞 글에서 본 것처럼 O(n)입니다. 그 뒤 n - 1번의 단계는 교환 한 번과 아래로 내리기 한 번이고, 아래로 내리기는 힙의 높이만큼인 O(log n)입니다. 그래서 전체는 O(n log n)이며, 입력이 어떻게 놓여 있든 이 한계가 지켜집니다. 값을 옮기는 일은 모두 리스트 안의 교환이라서 변수 몇 개 외의 추가 공간이 필요 없습니다. 이 글의 함수는 원본을 남기려고 처음에 복사하므로 그 O(n)만 더 씁니다.

힙 정렬은 병합 정렬처럼 최악의 경우에도 O(n log n)이고, 제자리 퀵 정렬처럼 추가 리스트가 필요 없다는 두 장점을 함께 가집니다. 그런데도 실제로는 퀵 정렬보다 느린 경우가 많습니다. 아래로 내리기는 인덱스 i에서 2i + 1로 건너뛰며 리스트의 멀리 떨어진 칸을 읽는데, 컴퓨터의 메모리는 가까운 칸을 이어서 읽을 때 훨씬 빠르기 때문입니다. 방금 읽은 칸의 가까운 칸을 곧 이어서 읽는 경향을 공간 지역성(spatial locality)이라 하며, 메모리가 캐시로 이 경향을 이용해 빨라지는 방식은 컴퓨터 구조 교재의 메모리 계층과 주기억장치에서 다룹니다. 그래서 힙 정렬은 단독으로 쓰기보다, 퀵 정렬에서 본 introsort처럼 퀵 정렬이 나쁜 분할을 만날 때 최악의 경우를 막는 안전장치로 자주 쓰입니다.

같은 키의 순서가 뒤집힌다

힙 정렬은 안정 정렬이 아닙니다. 루트와 활성 구간의 마지막 칸을 맞바꾸는 일은 멀리 떨어진 두 값을 바꾸는 것이라, 같은 키의 순서를 쉽게 뒤집습니다. 키가 같은 두 값만 있는 리스트로도 확인할 수 있습니다.

def sift_down_by_key(values, root, size):
    while 2 * root + 1 < size:
        child = 2 * root + 1
        if child + 1 < size and values[child + 1][0] > values[child][0]:
            child += 1
        if values[root][0] >= values[child][0]:
            return
        values[root], values[child] = values[child], values[root]
        root = child


def heap_sort_by_key(records):
    result = list(records)
    n = len(result)
    for root in range(n // 2 - 1, -1, -1):
        sift_down_by_key(result, root, n)
    for end in range(n - 1, 0, -1):
        result[0], result[end] = result[end], result[0]
        sift_down_by_key(result, 0, end)
    return result


print(heap_sort_by_key([(1, "가"), (1, "나")]))
print(heap_sort_by_key([(2, "가"), (1, "나"), (2, "다")]))

[(1, '나'), (1, '가')]
[(1, '나'), (2, '다'), (2, '가')]

첫 입력은 키가 같아 이미 최대 힙이고, 첫 단계에서 루트 (1, "가")와 마지막 칸 (1, "나")를 맞바꾸는 순간 순서가 뒤집힙니다. 두 번째 입력에서도 키가 2인 "가"와 "다"의 순서가 바뀌었습니다. 같은 키의 원래 순서가 중요하다면 병합 정렬이나 Python의 sorted처럼 안정 정렬을 써야 합니다.

더 깊이: 상위 k개만 필요할 때

전체를 정렬하지 않고 가장 큰 값 몇 개만 알고 싶을 때도 힙이 쓸모 있습니다. 점수 n개 가운데 상위 k개를 구한다고 해 봅시다. 크기가 k인 최소 힙을 두고, 점수를 하나씩 보면서 힙이 다 차지 않았으면 넣고, 다 찼으면 새 점수가 힙의 최솟값보다 클 때만 최솟값을 빼고 새 점수를 넣습니다. 그러면 힙에는 늘 지금까지 본 점수 가운데 큰 k개가 남고, 각 점수를 처리하는 비용은 O(log k)이므로 전체가 O(n log k)입니다. k가 n보다 훨씬 작으면 전체를 정렬하는 O(n log n)보다 빠르고, 힙에 k개만 두므로 점수가 한꺼번에 메모리에 들어가지 않아도 됩니다.

import heapq

scores = [72, 95, 88, 61, 99, 85, 90, 77]
top = []
for score in scores:
    if len(top) < 3:
        heapq.heappush(top, score)
    elif score > top[0]:
        heapq.heapreplace(top, score)
print(sorted(top, reverse=True))
print(heapq.nlargest(3, scores))

[99, 95, 90]
[99, 95, 90]

heapreplace는 최솟값을 꺼내고 새 값을 넣는 일을 한 번에 하는 함수입니다. top[0]은 최소 힙의 루트라서 지금까지 고른 세 점수 가운데 가장 작은 값입니다. 표준 라이브러리의 heapq.nlargest도 같은 결과를 돌려주며, 가장 작은 k개는 heapq.nsmallest로 구합니다.

정리

• 힙 정렬은 리스트 전체를 최대 힙으로 만든 뒤, 루트의 최댓값을 활성 구간의 마지막 칸과 맞바꾸고 활성 구간을 한 칸 줄여 다시 힙으로 고치는 일을 되풀이합니다.
• 활성 구간 [0, end)는 최대 힙이고 확정 구간 [end, n)은 가장 큰 값들이 오름차순으로 놓인 곳이며, 활성 구간의 값은 확정 구간의 값보다 크지 않습니다.
• sift_down에 활성 구간의 길이를 넘겨야 확정된 값이 다시 힙에 끌려 들어가지 않습니다.
• 힙 만들기 O(n)과 n - 1번의 O(log n) 복구로 최악의 경우에도 O(n log n)이고, 추가 공간은 O(1)입니다.
• 멀리 떨어진 값을 맞바꾸므로 안정 정렬이 아니며, 메모리를 멀리 건너뛰며 읽어 실제로는 퀵 정렬보다 느린 경우가 많습니다.

연습 문제

1. 첫 단계 따라가기

[3, 1, 2]를 힙 정렬할 때, 힙을 만든 직후와 첫 단계가 끝난 직후의 활성 구간과 확정 구간을 쓰세요.

2. 활성 구간을 줄이지 않으면

sift_down(result, 0, end)를 sift_down(result, 0, n)으로 바꾸면 [4, 1, 3, 2]의 결과는 어떻게 될까요?

def sift_down(values, root, size):
    while 2 * root + 1 < size:
        child = 2 * root + 1
        if child + 1 < size and values[child + 1] > values[child]:
            child += 1
        if values[root] >= values[child]:
            return
        values[root], values[child] = values[child], values[root]
        root = child


def heap_sort_wrong(values):
    result = list(values)
    n = len(result)
    for root in range(n // 2 - 1, -1, -1):
        sift_down(result, root, n)
    for end in range(n - 1, 0, -1):
        result[0], result[end] = result[end], result[0]
        sift_down(result, 0, n)
    return result


print(heap_sort_wrong([4, 1, 3, 2]))

[3, 4, 1, 2]

3. 상위 k개와 정렬 비용 비교하기

점수 100만 개에서 상위 10개를 구할 때, 전체를 정렬하는 방법과 크기 10인 최소 힙을 쓰는 방법의 비용을 대략 비교하세요.

다음 장의 정점·간선·인접 목록과 인접 행렬에서는 값들 사이의 연결 관계를 나타내는 그래프를 다룹니다. 힙은 8장의 Dijkstra 알고리즘에서 가장 가까운 정점을 고르는 우선순위 큐로 다시 등장합니다.