힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

개념

• 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식 
• 최대 힙 트리나 최소 힙 트리를 구성해 정렬
• 내림차순 정렬을 위해서는 최대 힙 구성, 오름차순 정렬 위해서는 최소 힙 구성 

과정

 

• 최대 값을 하나씩 뽑아내면서 정렬 

코드 

# Max Heapify 함수: 특정 인덱스의 노드를 최대 힙 형태로 유지하는 함수
def max_heapify(arr, n, i):
    largest = i  # 부모 노드의 인덱스로 초기화
    left = 2 * i + 1  # 왼쪽 자식 노드의 인덱스
    right = 2 * i + 2  # 오른쪽 자식 노드의 인덱스

    # 왼쪽 자식 노드가 부모 노드보다 크면 largest 값을 갱신
    if left < n and arr[largest] < arr[left]:
        largest = left

    # 오른쪽 자식 노드가 부모 노드보다 크면 largest 값을 갱신
    if right < n and arr[largest] < arr[right]:
        largest = right

    # largest 값이 갱신되었다면 노드를 교환하고, 재귀적으로 Max Heapify를 호출
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        max_heapify(arr, n, largest)

# 힙 정렬 함수
def heap_sort(arr):
    n = len(arr)

    # 입력 배열을 최대 힙 형태로 만듦
    for i in range(n // 2 - 1, -1, -1):
        max_heapify(arr, n, i)

    # 힙에서 최대 원소를 추출하고 정렬된 부분에 추가
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 최대 원소를 맨 뒤로 이동
        max_heapify(arr, i, 0)  # 힙 속성 유지

    return arr

# 테스트용 입력 배열
arr = [4, 10, 3, 5, 1]
sorted_arr = heap_sort(arr)

print("힙 정렬 결과:", sorted_arr)

 

특징

• 장점
  • 안정적인 정렬 알고리즘
  • 최악의 경우에도 시간 복잡도가 O(NlogN)으로 효율적
• 단점
  • 힙 정렬은 비교 기반의 정렬 알고리즘이므로 비교 연산이 많이 필요
  • 원본 배열을 파괴하므로 정렬되지 않은 배열의 복사본 필요 

시간 복잡도

• O(Nlog2N)

 

참고

https://gr-st-dev.tistory.com/1935

파이썬을 사용한 힙 정렬 알고리즘 - 효율적인 정렬 방법