힙정렬의 개념
힙정렬(Heap Sort)은 힙(Heap)이라는 자료구조를 사용하는 정렬 알고리즘입니다. 힙은 완전 이진 트리로 구성된 특수한 구조를 가지고 있는데, 힙을 이용해 배열을 정렬하는 방식입니다.
힙의 구조
힙은 이진 트리의 일종으로, 각 노드의 값이 자식 노드의 값보다 크거나 작은 특성을 가집니다. 크게 두 가지 유형이 있는데요:
- 최대 힙(Max Heap)**: 부모 노드가 자식 노드보다 항상 크거나 같으며, 루트 노드가 최댓값입니다.
- 최소 힙(Min Heap)**: 부모 노드가 자식 노드보다 항상 작거나 같으며, 루트 노드가 최솟값입니다.
힙정렬에서 보통 최대 힙을 사용하여 내림차순 정렬을 구현합니다. 배열을 힙으로 변환한 후, 루트 노드에 위치한 최대값을 하나씩 제거해 나가는 방식으로 정렬을 진행합니다.
힙정렬의 과정
1. 힙 구성(Build Heap): 주어진 배열을 힙 구조로 재배열합니다.
2. 최댓값 추출(Extract Max): 힙에서 루트 노드를 제거하고 남은 트리를 다시 힙으로 정렬합니다.
3. 정렬 완료: 힙에 원소가 남지 않으면 정렬이 완료됩니다.
힙정렬의 시간복잡도
힙정렬의 가장 큰 장점은 O(n log n)의 시간복잡도를 유지한다는 것입니다. 이 성능은 평균과 최악의 경우에도 동일하게 유지되므로, 많은 양의 데이터를 다룰 때 유용합니다.
- 힙 구성: 힙을 만드는 데 걸리는 시간은 O(n)입니다. 배열을 힙 구조로 만드는 `buildHeap()` 단계에서 전체 트리의 높이에 따라 연산이 이루어지기 때문에 선형 시간이 소요됩니다.
- 정렬 과정: 힙에서 루트 노드를 제거하고 재정렬하는 과정은 각 단계에서 O(log n)의 시간이 걸립니다. 총 n개의 노드에 대해 반복되므로 O(n log n)의 시간이 소요됩니다.
힙정렬의 예제
배열 [4, 10, 3, 5, 1]을 힙정렬로 정렬하기
1. 배열을 최대 힙으로 변환:
초기 배열: `[4, 10, 3, 5, 1]`
최대 힙으로 변환한 후: `[10, 5, 3, 4, 1]`
2. 루트 노드를 제거하고, 다시 힙으로 정렬:
`[1, 5, 3, 4]` -> 힙 정렬 후: `[5, 4, 3, 1]`
3. 반복해서 루트 노드를 제거하고 정렬하면 최종적으로 `[1, 3, 4, 5, 10]`이 됩니다.
힙정렬의 파이썬 코드
def heapify(arr, n, i):
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)
def heap_sort(arr):
n = len(arr)
# Build a maxheap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements from the heap
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("Sorted array:", arr)
