Heap Sort: 힙(Heap) 자료구조를 이용한 효율적인 정렬 알고리즘
Heap Sort는 힙(Heap)이라는 자료구조를 활용하여 데이터를 정렬하는 알고리즘입니다. 힙은 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구성되며, Heap Sort는 일반적으로 최대 힙을 사용합니다. 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 가지는 효율적인 정렬 알고리즘입니다.
1. 개념
힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 특성을 가지는 자료구조입니다.
- 최대 힙(Max Heap): 부모 노드의 키(Key)가 자식 노드의 키보다 크거나 같은 힙
- 최소 힙(Min Heap): 부모 노드의 키(Key)가 자식 노드의 키보다 작거나 같은 힙
Heap Sort는 최대 힙을 사용하여 정렬을 수행합니다. 최대 힙에서 가장 큰 값은 항상 루트 노드에 위치하므로, 루트 노드를 꺼내어 정렬된 배열의 뒤쪽에 배치하는 과정을 반복합니다.
2. 왜 사용하는가
Heap Sort는 다음과 같은 장점을 가집니다.
- 안정적인 성능: 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 보장합니다.
- 메모리 효율성: 추가적인 메모리 공간을 거의 사용하지 않는 제자리 정렬(In-place Sort)입니다. (O(1)의 추가 공간)
하지만, 삽입 정렬(Insertion Sort)이나 병합 정렬(Merge Sort)에 비해 구현이 복잡하고, 실제 데이터에 따라 성능 차이가 발생할 수 있습니다.
3. 동작 원리
Heap Sort는 크게 두 단계로 이루어집니다.
- 힙 구성(Heapify): 주어진 데이터를 최대 힙으로 만듭니다.
- 정렬(Sorting): 힙의 루트 노드(최대 값)를 꺼내어 정렬된 배열의 뒤쪽에 배치하고, 힙을 재구성합니다. 이 과정을 반복하여 정렬을 완료합니다.
힙 구성(Heapify) 과정:
- 아래에서부터 위로 올라가며 각 노드를 힙의 규칙에 맞게 조정합니다.
- 자식 노드와 비교하여 더 큰 값을 부모 노드로 이동시킵니다.
정렬 과정:
- 루트 노드(최대 값)를 배열의 마지막 위치와 교환합니다.
- 힙의 크기를 줄이고, 새로운 루트 노드를 힙의 규칙에 맞게 조정합니다.
- 위 과정을 반복합니다.
4. 코드 예제
def heapify(arr, n, i):
largest = i # 현재 노드를 가장 큰 값으로 초기화
left = 2 * i + 1 # 왼쪽 자식 노드
right = 2 * i + 2 # 오른쪽 자식 노드
# 왼쪽 자식 노드가 현재 노드보다 크면
if left < n and arr[left] > arr[largest]:
largest = left
# 오른쪽 자식 노드가 현재 노드보다 크면
if right < n and arr[right] > arr[largest]:
largest = right
# 가장 큰 값이 현재 노드가 아니면
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # 교환
heapify(arr, n, largest) # 재귀적으로 힙 구성
def heap_sort(arr):
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) # 힙 재구성
# 예제
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("정렬된 배열:", arr)5. 시간 복잡도 또는 성능 특성
- 최고의 경우: O(n log n)
- 평균의 경우: O(n log n)
- 최악의 경우: O(n log n)
- 공간 복잡도: O(1) (제자리 정렬)
힙 구성 과정은 O(n) 시간이 소요되고, 정렬 과정은 O(n log n) 시간이 소요됩니다. 따라서 전체 시간 복잡도는 O(n log n)입니다.
6. 실무 사용 사례
Heap Sort는 다음과 같은 경우에 사용될 수 있습니다.
- 메모리 제약이 있는 환경: 제자리 정렬이기 때문에 메모리 사용량이 적습니다.
- 성능 예측 가능성이 중요한 경우: 항상 O(n log n)의 성능을 보장합니다.
- 우선순위 큐(Priority Queue) 구현: 힙 자료구조는 우선순위 큐를 구현하는 데 효과적입니다.
7. 주의할 점
- Heap Sort는 삽입 정렬이나 병합 정렬에 비해 구현이 복잡합니다.
- 실제 데이터에 따라 성능 차이가 발생할 수 있습니다.
- 힙 자료구조에 대한 이해가 필요합니다.
8. 핵심 정리
Heap Sort는 힙(Heap) 자료구조를 활용하여 데이터를 정렬하는 효율적인 알고리즘입니다. O(n log n)의 시간 복잡도를 가지며, 제자리 정렬(In-place Sort)이라는 장점을 가지고 있습니다. 메모리 제약이 있거나 성능 예측 가능성이 중요한 경우에 유용하게 사용할 수 있습니다.