힙 정렬 (Heap Sort)

힙 정렬(Heap Sort)은 완전 이진 트리(Complete Binary Tree) 기반의 정렬 알고리즘으로, 힙(heap) 자료 구조를 이용하여 정렬을 수행한다. 힙 정렬은 최악의 경우에도 O(n log n)의 시간 복잡도를 가지며, 안정 정렬은 아니지만 제자리 정렬(In-place Sorting)이다.

알고리즘 개념

힙 정렬은 다음 두 가지 단계로 이루어진다:

1. 최대 힙 구성 (Build Max Heap):
   • 주어진 배열을 최대 힙(Max Heap)으로 변환한다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리이다.
2. 힙에서 요소 추출 및 정렬 (Extract Elements from Heap):
   • 최대 힙에서 루트 노드(가장 큰 값)를 추출하여 배열의 끝으로 이동시키고, 힙의 크기를 줄인 후 다시 힙 속성을 유지한다. 이 과정을 반복하여 전체 배열을 정렬한다.

시간 복잡도

힙 정렬의 시간 복잡도는 다음과 같다:

• 최선의 경우 (Best Case): O(n log n)
• 평균 경우 (Average Case): O(n log n)
• 최악의 경우 (Worst Case): O(n log n)

공간 복잡도

힙 정렬의 공간 복잡도는 O(1)이다. 이는 힙 정렬이 제자리 정렬(In-place Sorting) 알고리즘이기 때문이다. 정렬 과정에서 추가적인 메모리를 거의 사용하지 않는다.

구현 방법

힙 정렬은 다음 세 가지 주요 함수로 구현된다:

1. 힙 속성 유지 (Heapify):
   • 특정 노드가 힙 속성을 위반하는 경우, 자식 노드들과 교환하여 힙 속성을 복구하는 역할을 한다. 이 과정을 재귀적으로 수행한다.
2. 최대 힙 구성 (Build Max Heap):
   • 주어진 배열을 최대 힙으로 변환한다. 배열의 중간부터 시작하여 첫 번째 요소까지 역순으로 heapify를 호출한다.
3. 힙 정렬 (Heap Sort):
   • 최대 힙에서 루트 노드를 추출하여 배열의 끝으로 이동시키고, 힙의 크기를 줄인 후 다시 힙 속성을 유지하는 과정을 반복한다.

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 build_max_heap(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

def heap_sort(arr):
    n = len(arr)

    build_max_heap(arr)

    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("Sorted array is:", arr)

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms