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

최댓값을 끝에 옮긴 뒤 루트만 복구하며 전체 정렬을 완성합니다.

최댓값을 반복해서 꺼내면 내림차순으로 얻을 수 있습니다. 최대 힙의 최댓값을 목록 끝에 고정하면 오름차순 정렬도 만들 수 있습니다. 목표는 힙으로 유지할 활성 구간과 이미 정렬된 오른쪽 구간을 구분하는 것입니다. 앞 본문의 인덱스와 sift-down을 복습하세요.

개념과 약속

처음 전체를 최대 힙으로 만듭니다. 루트와 활성 구간의 마지막 원소를 교환하면 최댓값이 최종 위치에 갑니다. 마지막 칸을 활성 구간에서 제외한 뒤 루트의 새 값을 sift_down으로 내려 힙을 복구합니다. 다음 최댓값도 바로 왼쪽에 고정합니다.

end는 오른쪽 확정 구간 앞의 마지막 활성 위치입니다. sift_down(..., end)의 크기는 end 위치를 제외한 칸 수라서, 이제 확정된 최댓값을 다시 움직이지 않습니다. 이 구현은 작업 목록을 복사하지만 그 복사 안에서는 교환과 몇 개 변수로 진행합니다.

손으로 상태 추적하기

단계	활성 힙	오른쪽 확정 구간
`[4,1,3,2]`를 힙으로	`[4,2,3,1]`	없음
루트 4 고정·복구	`[3,2,1]`	`[4]`
루트 3 고정·복구	`[2,1]`	`[3,4]`
루트 2 고정	`[1]`	`[2,3,4]`

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

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 build_max_heap(values):
    result = list(values)
    for root in range(len(result) // 2 - 1, -1, -1):
        sift_down(result, root, len(result))
    return result


def heap_sort(values):
    result = build_max_heap(values)
    for end in range(len(result) - 1, 0, -1):
        result[0], result[end] = result[end], result[0]
        sift_down(result, 0, end)
    return result


values = [4, 1, 3, 2]
print(heap_sort(values))
print(heap_sort([2, 2, 1]))
print(heap_sort([]))
print(values)