[파이썬] 힙 정렬 (Heap Sort)의 원리와 구현

01 Sep 2023

python

힙 정렬 (Heap Sort)은 정렬 알고리즘 중 하나로, 힙 자료구조를 기반으로 동작합니다. 힙 정렬은 평균 시간 복잡도와 최악 시간 복잡도 모두 O(n log n)으로 빠른 정렬 알고리즘입니다. 이번 포스트에서는 힙 정렬 알고리즘의 원리와 python으로의 구현에 대해 알아보겠습니다.

힙 정렬의 원리

힙 정렬은 크기를 갖는 힙 트리를 이용하여 정렬을 수행합니다. 힙 트리는 부모 노드의 값이 자식 노드의 값보다 항상 큰 트리 구조입니다. 트리의 가장 위에 있는 노드를 루트 노드라고 합니다.

힙 정렬의 원리는 다음과 같습니다:

정렬할 리스트를 입력받습니다.
리스트를 힙 구조로 변환합니다.
힙에서 가장 큰 요소(루트 노드)를 추출합니다.
추출한 요소를 정렬된 리스트에 추가합니다.
힙의 크기를 줄이고, 다시 2단계부터 반복합니다.
힙이 비어있을 때까지 반복하여 정렬된 리스트를 얻습니다.

힙 정렬의 구현 (python)

# 힙을 구성하는 함수
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)  # 힙 구성

    return arr


# 힙 정렬 사용 예시
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print("정렬된 배열:", sorted_arr)

위의 코드는 python으로 힙 정렬 알고리즘을 구현한 예시입니다. heapify 함수는 힙을 구성하기 위해 사용되고, heap_sort 함수는 힙 정렬을 수행합니다. arr 리스트에 정렬할 값들을 입력하고, heap_sort(arr)를 호출하여 정렬된 결과를 얻을 수 있습니다.

힙 정렬은 자료구조인 힙에 기반하므로, 입력 크기에 따라 효율적인 정렬을 수행할 수 있습니다. 시간 복잡도가 O(n log n)이기 때문에 대량의 데이터에도 빠르게 정렬할 수 있는 장점이 있습니다.