힙 정렬(Heap Sort) 의 개념
힙 정렬은 힙 자료구조의 장점을 사용해 데이터를 정렬하는 방식입니다. 이를 이해하기 위해서 힙이라는 자료구조에 대해서 먼저 알아야 하는데, 힙은 완전 이진 트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리) 로서 아래의 조건을 만족하는 자료구조입니다.
- 최대 힙: 각 노드의 값이 자신의 자식 노드의 값보다 크거나 같다는 조건을 만족
- 최소 힙: 각 노드의 값이 자신의 자식 노드의 값보다 작거나 같다는 조건을 만족
최대 힙에 새로운 값을 삽입할 때에는 삽입 후 최대 힙의 조건을 만족시키는 교환을 수행하고, 최댓값을 삭제할 때에는 루트 노드의 값과 힙의 마지막 노드를 교환한 후 교환을 통해서 힙으로 재구성하는 과정을 수행합니다.
힙 정렬은 입력 데이터인 배열을 초기 힙으로 변환하고, 최댓값을 삭제한 후 힙으로 재구성하는 과정을 데이터의 개수만큼 반복하는 방식입니다.
힙 정렬의 Python 구현
Python 으로 퀵 정렬을 아래와 같이 구현할 수 있습니다.
def heap_sort(arr: list) -> list:
n = len(arr)
# 배열을 최대 힙 구조로 만듭니다.
for i in range(n // 2 - 1, -1, -1):
_heapify(arr, n, i)
# 배열을 정렬합니다.
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
_heapify(arr, i, 0)
return arr # 정렬된 배열을 반환합니다.
def _heapify(arr: list, n: int, i: int) -> None:
largest = i # 가장 큰 값을 가진 노드
left = 2 * i + 1 # 왼쪽 자식 노드
right = 2 * i + 2 # 오른쪽 자식 노드
# 왼쪽 자식 노드가 존재하고, 루트 노드보다 큰 경우
if left < n and arr[i] < arr[left]:
largest = left
# 오른쪽 자식 노드가 존재하고, 루트 노드보다 큰 경우
if right < n and arr[largest] < arr[right]:
largest = right
# 루트 노드가 가장 큰 값이 아닌 경우
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # 루트 노드와 가장 큰 값을 가진 노드를 교환
_heapify(arr, n, largest) # 교환된 노드에서 heapify를 다시 수행
힙 정렬은 배열을 최대 힙 구조로 만드는 _heapify 함수와 그것을 반복해 정렬을 수행하는 heap_sort 로 구성됩니다. 위의 코드는 아래와 같이 동작합니다.
먼저, 이해를 돕기 위해서 최대 힙을 일차원 배열로 나타낼 수 있다는 것을 짚고 넘어갈 필요가 있습니다. 트리의 각 노드에 대해서 루트 노드에서 리프 노드 쪽으로 – 같은 레벨에서는 왼쪽에서 오른쪽으로 순서대로 인덱스를 부여하면 됩니다. 예컨대 아래와 같습니다.
# 최대 힙
80(0)
60(1) 70(2)
40(3) 20(4) 30(5) 50(6)
10(7)
# 최대 힙을 배열로
arr = [80, 60, 70, 40, 30, 20, 30, 50, 10]
이렇게 일차원 배열로 힙을 구현하면, 인덱스를 사용해 자식 노드를 찾는 것, 자식 노드에서 부모 노드를 찾는 것 모두 간단하게 수행할 수 있습니다.
예컨대, 위의 최대 힙에서 60의 인덱스는 1인데, 인덱스 * 2 + 1, 인덱스 * 2 + 2 를 통해서 왼쪽과 오른쪽 노드의 위치를 찾을 수 있죠. (3, 4)
정리해보자면,
- 자식 노드를 찾을 때는
인덱스 * 2 + 1, 인덱스 * 2 + 2를, - 부모 노드를 찾을 때는
인덱스 - 1 / 2를 사용할 수 있습니다.
자, 그러면 위의 지식을 기반으로 merge_sort 구현을 다시 살펴봅시다.
[12, 11, 13, 5, 7, 6]
이 상황에서 배열은 첫 번째 반복문을 만납니다. 배열의 중간부터 시작하여, 루트 노드까지 반복하면서 _heapify 를 호출하고 있죠? 배열의 중간부터 이를 시작하는 이유는 이미 배열이 힙 속성을 만족하기 때문입니다.
[12, 11, 13, 5, 7, 6]
-> 힙으로 변환
12
11 13
5 7 6
-> 5, 7, 6 은 힙 구조를 만족인덱스대로 완전 이진 트리를 구성하면, 5, 7, 6 처럼 리프 노드가 없는 노드들은 그 자체로 최대 힙 구조를 만족시키게 됩니다.(리프 노드가 없으므로, 해당 노드들은 자신의 자식 노드들보다 무조건 크거나 같은 값을 가지는 노드가 됩니다.)
그렇기 때문에 배열의 중간부터 루트까지 시작하는 것이 합리적인 방식입니다. 힙 조건을 만족시키지 않는 배열의 부분부터 시작하므로, 첫 번째 _heapify 는 아래와 같이 호출되겠죠?
_heapify(arr, n, i)
# heapify([12, 11, 13, 5, 7, 6], 5, 2]_heapify 안에서, 가장 먼저 수행하는 작업은 루트 노드와 왼쪽 자식 노드, 오른쪽 자식 노드를 설정하는 것입니다. 위에서 완전 이진 트리를 배열로 나타내면 인덱스를 통해서 왼쪽, 오른쪽 자식 노드를 쉽게 찾을 수 있었습니다.
- 자식 노드를 찾을 때는
인덱스 * 2 + 1, 인덱스 * 2 + 2를,- 부모 노드를 찾을 때는
인덱스 - 1 / 2를 사용할 수 있습니다.
그래서, 각각 왼쪽과 오른쪽 자식 노드가 존재하고 루트 노드보다 큰 경우, 큰 노드를 largest 라는 변수에 저장하게 됩니다.
# 왼쪽 자식 노드가 존재하고, 루트 노드보다 큰 경우
if left < n and arr[i] < arr[left]:
largest = left
# 오른쪽 자식 노드가 존재하고, 루트 노드보다 큰 경우
if right < n and arr[largest] < arr[right]:
largest = right
위의 과정을 거친 후 루트 노드가 가장 큰 값이 아닌 경우, 루트 노드와 가장 큰 값을 가진 노드를 교환합니다. 이렇게 함으로서 루트 노드는 항상 최대 값을 유지할 수 있고, 재귀적으로 _heapify 를 호출하여 결과적으로 전체 배열을 최대 힙 구조로 만들게 됩니다.
13
11 12
5 6 7
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
_heapify(arr, i, 0)이제 최대 힙 구조로 만들어진 배열을 정렬하는 과정을 거칩니다. 배열의 마지막 요소부터 첫 번째 요소까지 현재 인덱스를 루트 노드와 교환하고, 교환된 배열의 마지막 부분을 제외하고 힙을 다시 구성합니다. 그러면 배열은 점차 정렬된 상태가 되는데, 이 방식을 힙 정렬이라고 합니다.
힙 정렬의 성능 분석과 특징
- 힙 정렬은 최선, 최악, 평균의 경우 모두
O(nlogn)의 시간복잡도를 가집니다. - 힙 정렬은 안정적이지 않은 정렬 알고리즘입니다.
- 힙 정렬은 입력 배열과 입력 크기를 제외하고 필요한 저장공간의 개수가 상수 개인 제자리 정렬 알고리즘입니다.