[python] 힙 정렬

07 Dec 2023

python

힙 정렬은 선택 정렬의 대안으로 사용되는 정렬 알고리즘입니다. 힙은 완전 이진 트리로 구성되어 있으며, 힙 정렬은 이러한 힙을 이용하여 정렬을 수행합니다.

알고리즘 원리

주어진 배열을 최대 힙 형태로 구성합니다.
최대 힙에서 가장 큰 요소(루트)를 꺼내고, 배열의 끝과 교환합니다.
배열의 크기를 1만큼 감소시킨 뒤, 변경된 루트로부터 다시 최대 힙을 구성합니다.
위 과정을 배열의 크기가 1이 될 때까지 반복합니다.

예시 코드

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)
  
    # 최대 힙 구성
    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, 6, 7, 11, 12, 13]

시간 복잡도

힙 생성: O(n)
힙 정렬: O(n log n)

결론

힙 정렬은 최대 힙을 활용하여 정렬을 수행하는 효율적인 알고리즘입니다. 선택 정렬보다 시간 복잡도가 효율적이기 때문에, 대량의 데이터를 정렬할 때 유용하게 사용될 수 있습니다.