힙 정렬 (Heap Sort)

힙 정렬

"힙(Heap) 자료구조를 이용해 정렬하는 알고리즘"

• 완전 이진 트리(Complete Binary Tree) 기반의 힙(Heap) 구조 사용
• 최대 힙(Max Heap) → 내림차순 정렬 / 최소 힙(Min Heap) → 오름차순 정렬
• 시간복잡도 O(n log n) → 퀵 정렬처럼 빠르지만, 안정 정렬(Stable Sort)이 아님
• 제자리 정렬(In-place Sort) 가능 → 추가 메모리 사용 X (O(1))

2025.01.20 - [데이터 사이언스/알고리즘] - 완전 이진 트리 (Complete Binary Tree)

---

힙 정렬의 동작 원리

1. 힙 생성(Heapify) → 주어진 배열을 힙 구조로 변환
2. 최댓값(또는 최솟값) 추출 → 루트 노드(가장 큰/작은 값)를 배열의 끝으로 이동
3. 힙 속성 복구 → 남은 힙을 다시 정렬하고 반복

2025.01.20 - [데이터 사이언스/알고리즘] - Heapify

---

힙 정렬의 시간복잡도

경우	시간복잡도
최선 (이미 정렬됨)	O(n log n)
평균	O(n log n)
최악 (역순 정렬)	O(n log n)

 

✅ 퀵 정렬과 달리, 최악의 경우에도 O(n log n) 성능 유지!
✅ 추가 메모리 사용 없이 O(1) 공간복잡도로 정렬 가능!

# Pseudo Code
FUNCTION HeapSort(arr)
    n = length(arr)

    # 1. 주어진 배열을 최대 힙으로 변환 (Heapify)
    FOR i FROM (n // 2) DOWNTO 0 DO
        Heapify(arr, n, i)

    # 2. 힙에서 최대값을 하나씩 꺼내 정렬
    FOR i FROM n-1 DOWNTO 1 DO
        SWAP arr[0] AND arr[i]  # 루트(최대값)를 마지막으로 이동
        Heapify(arr, i, 0)  # 힙 크기를 줄이고 다시 Heapify 실행

END FUNCTION

FUNCTION Heapify(arr, n, i)
    largest = i  # 현재 부모 노드
    left = 2 * i + 1  # 왼쪽 자식 노드
    right = 2 * i + 2  # 오른쪽 자식 노드

    # 왼쪽 자식이 존재하고, 부모보다 크다면 largest 갱신
    IF left < n AND arr[left] > arr[largest] THEN
        largest = left

    # 오른쪽 자식이 존재하고, 가장 큰 값보다 크다면 largest 갱신
    IF right < n AND arr[right] > arr[largest] THEN
        largest = right

    # 부모가 가장 큰 값이 아니라면 Swap 실행 후, Heapify 재귀 호출
    IF largest != i THEN
        SWAP arr[i] AND arr[largest]
        Heapify(arr, n, largest)

END FUNCTION


# Full Code
def heapify(arr, n, i):
    largest = i  # 부모 노드 인덱스
    left = 2 * i + 1  # 왼쪽 자식 노드
    right = 2 * i + 2  # 오른쪽 자식 노드

    # 왼쪽 자식이 부모보다 크다면 largest 업데이트
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 오른쪽 자식이 가장 크다면 largest 업데이트
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 부모가 가장 크지 않다면 Swap 실행 후, 재귀적으로 Heapify 실행
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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

    # 1. 최대 힙(Max Heap) 생성
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2. 힙에서 하나씩 꺼내 정렬
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 최대값을 끝으로 이동
        heapify(arr, i, 0)  # 힙 크기 줄이고 Heapify 실행


# 테스트
arr = [10, 9, 5, 8, 3, 2, 1, 6, 7, 4]
heap_sort(arr)
print("힙 정렬 결과:", arr)

---

장점

• 최악의 경우에도 O(n log n) 보장 (퀵 정렬보다 안정적)
• 제자리 정렬 가능 → 추가적인 메모리(O(1))만 사용
• 큰 데이터셋에서도 안정적인 성능 유지

단점

• Stable Sort(안정 정렬)이 아님 → 같은 값의 순서가 유지되지 않음
• 힙 구성(Heapify) 과정에서 연산량이 많아 실제 성능은 퀵 정렬보다 느릴 수도 있음
• 캐시 효율성이 낮아 실제 실행 속도가 퀵 정렬보다 떨어질 수 있음

결론

힙 정렬은 퀵 정렬보다 안정적인 O(n log n) 성능을 보장하지만, 실제 실행 속도는 퀵 정렬보다 느릴 수도 있습니다.