힙 정렬(Heap Sort)은 이진 힙(Binary Heap) 자료구조를 기반으로 하는 정렬 기법입니다. 힙 정렬을 제대로 이해하려면 먼저 이진 트리(Binary Tree)와 이진 힙에 대한 개념을 알고 있어야 합니다.
완전 이진 트리(Complete Binary Tree)란?
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있는 트리 자료구조를 말합니다. 마지막 레벨의 노드들은 반드시 왼쪽부터 순서대로 채워져야 합니다.
이진 힙(Binary Heap)이란?
이진 힙은 이진 트리의 특수한 형태로, 부모 노드와 자식 노드 간의 크기 관계가 항상 유지되는 구조입니다. 이진 힙은 다음 두 가지 종류로 나눌 수 있습니다.
최대 힙(Max Heap) − 각 레벨에서 부모 노드가 자식 노드보다 항상 큽니다.
최소 힙(Min Heap) − 각 레벨에서 부모 노드가 자식 노드보다 항상 작습니다.
완전 이진 트리의 배열 표현
이진 힙은 배열로 표현할 수 있으며, 이는 메모리 측면에서 매우 효율적입니다. 인덱스가 0부터 시작한다고 가정할 때, 부모 노드가 인덱스 i에 저장되어 있다면 다음과 같이 계산할 수 있습니다.
- 왼쪽 자식 노드:
2 * i + 1 - 오른쪽 자식 노드:
2 * i + 2
힙 정렬 알고리즘
힙 정렬은 다음 세 단계로 진행됩니다.
완전 이진 트리로부터 최대 힙을 구축합니다.
루트(최댓값)를 제거하고 힙의 마지막 요소와 교체한 뒤, 힙 크기를 1 줄입니다. 그리고 남은 노드들로 다시 최대 힙을 구축합니다.
노드가 1개만 남을 때까지 2번 과정을 반복합니다.
최대 힙 구축하기 (Heapify)
아래 코드는 완전 이진 트리에서 최대 힙을 만드는 heapify 함수입니다. 루트와 두 자식 노드를 비교하여 가장 큰 값이 루트가 아니라면, 가장 큰 값을 루트와 교환합니다. 이 과정은 재귀적으로 수행되며, 자식 노드보다 작은 현재 루트는 올바른 위치에 도달할 때까지 하위 서브트리들과 계속 비교됩니다.
def heapify(arr, n, i):
# 루트와 자식 노드 중 가장 큰 값 찾기
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# 루트가 가장 큰 값이 아니라면 교환하고 재귀적으로 heapify 진행
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)다음 코드는 정렬하고자 하는 배열(즉, 완전 이진 트리)로부터 최대 힙을 구축합니다.
힙 정렬 수행하기
최대 힙이 준비되었다면, 이제 다음 작업들을 수행합니다.
루트(최댓값)를 힙의 마지막 요소와 교환합니다.
힙의 크기를 1 줄입니다. (가장 큰 요소가 이미 마지막 위치에 도착했으므로 더 이상 고려하지 않습니다.)
마지막 요소를 제외한 나머지 노드들로 최대 힙을 다시 구축합니다.
요소가 1개만 남을 때까지 위 과정을 반복합니다.
for i in range(n-1, 0, -1):
# 교환(Swap)
arr[i], arr[0] = arr[0], arr[i]
# 루트 요소 heapify
heapify(arr, i, 0)파이썬 힙 정렬 전체 코드
지금까지 설명한 내용을 모두 합친 파이썬 힙 정렬 전체 프로그램은 다음과 같습니다.
def heapify(arr, n, i):
# 루트와 자식 노드 중 가장 큰 값 찾기
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# 루트가 가장 큰 값이 아니라면 교환하고 재귀적으로 heapify 진행
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# 최대 힙 구축
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# 교환(Swap)
arr[i], arr[0] = arr[0], arr[i]
# 루트 요소 heapify
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print(arr[i], end=' ')위 프로그램을 실행하면 [1, 5, 6, 9, 10, 12]와 같이 오름차순으로 정렬된 결과를 확인할 수 있습니다.
시간 복잡도
힙 정렬의 시간 복잡도는 O(n log n)입니다. 힙 구축 단계와 각 요소 추출 시마다 log n의 연산이 n번 반복되기 때문입니다. 또한 추가적인 메모리 공간 없이 제자리(in-place) 정렬이 가능하다는 장점이 있어, 안정적인 성능이 필요한 경우에 널리 활용됩니다.