힙 정렬
힙은 '부모의 값 ≥ 자식의 값'인 관계가 항상 성립하는 완전 이진 트리입니다. 모든 자식의 노드가 2개인 트리 구조라는 것입니다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙입니다. 즉, 이러한 두 값의 대소관계가 일정하면 됩니다.
힙은 부모-자식 관계는 일정하지만, 형제 사이의 관계는 일정하지 않습니다. 아래 그림과 같이 7이 6보다 왼쪽에, 5와 4가 3과 2보다 왼쪽에 있지만, 아래 2와1보다 큰 3이 오른쪽에 있는 것처럼 말입니다. 이러한 이유로 부분 순서 트리라고도 합니다.
힙 정렬에서 배열의 인덱스는 다음과 같습니다. 이러한 순서로 배열을 힙에 저장하면 부모, 오른쪽 자식, 왼쪽 자식과는 다음과 같은 관계가 성립합니다.
원소 a[i]
① 부모: a[(i - 1) // 2]
② 왼쪽 자식: a[i * 2 + 1]
③ 오른쪽 자식: a[i * 2 + 2]
힙 정렬 배열이 정렬된 배열인가?
힙 정렬은 다음과 같은 과정을 반복합니다.
1. 힙에서 최대값인 루트를 꺼냅니다.
2. 루트 이외의 부분을 힙으로 만듭니다.
즉, 루트를 꺼낸 후 다음과 같은 과정을 통해 힙을 재구성해야합니다. 이렇게 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성됩니다.
꺼낸 값을 나열하기
① 루트 a[0]에 위치한 최댓값을 꺼내고 배열의 맨 끝 원소인 a[9]와 교환
② a[0] ~ a[8] 힙으로 만들기
③ 다시 a[0]에 위치한 두번째 최댓값을 꺼내고 a[8]과 교환
④ 반복
배열을 힙으로 만들기
가장 아랫부분의 오른쪽 서브트리의 힙을 만들고, 같은 단계에 있는 왼쪽 서브트리로 진행합니다. 그 단계를 완료하면 한 단계 위로 이동하면서 각각의 서브트리를 힙으로 만듭니다.
def down_heap(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 힙으로 만들기"""
temp = a[left]
parent = left
while parent < (right + 1) // 2:
cl = parent * 2 + 1
cr = cl + 1
child = cr if cr <= right and a[cr] > a[cl] else cl
if temp >= a[child]:
break
a[parent] = a[child]
parent = child
a[parent] = temp
최종 코드
def heap_sort(a: MutableSequence) -> None:
"""힙 정렬"""
def down_heap(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 힙으로 만들기"""
temp = a[left]
parent = left
while parent < (right + 1) // 2:
cl = parent * 2 + 1
cr = cl + 1
child = cr if cr <= right and a[cr] > a[cl] else cl
if temp >= a[child]:
break
a[parent] = a[child]
parent = child
a[parent] = temp
n = len(a)
""" 1단계 a[i] ~ a[n-1]을 힙으로 만들기 """
for i in range((n-1) // 2, -1, -1):
down_heap(a, i, n-1)
""" 2단계 """
for i in range(n - 1, 0, -1):
a[0], a[i] = a[i], a[0] # 최댓값인 a[0]과 마지막 원소 교환
down_heap(a, 0, i-1) # a[0] ~ a[n-1]을 힙으로 만들기