힙 정렬(Heap Sort) 알고리즘

개요

힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 기반으로 하는 비교 기반 정렬 알고리즘이다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 이용해 최댓값(또는 최솟값)을 반복적으로 추출하고, 이를 배열의 끝에 삽입하는 방식으로 동작한다. **시간 복잡도가 항상 O(n log n)**으로 일정하며, **제자리 정렬(in-place)**이 가능하다는 장점이 있다.

---

1. 개념 및 정의

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

1. 배열을 힙 구조(완전 이진 트리)로 구성 (heapify)
2. 루트 노드(최댓값 또는 최솟값)를 추출한 뒤, 남은 요소로 힙 재구성 → 정렬 반복

일반적으로 최대 힙을 사용해 오름차순 정렬을 수행한다.

---

2. 동작 원리

단계	설명
1단계	입력 배열을 최대 힙 구조로 변환
2단계	힙의 루트(최댓값)를 마지막 요소와 교환
3단계	힙 크기를 줄이고 다시 heapify 수행
4단계	모든 요소가 정렬될 때까지 반복

최대 힙은 부모 노드가 자식보다 항상 크다는 구조를 이용한다.

---

3. 파이썬 구현 예시

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        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

# 사용 예시
print(heap_sort([4, 10, 3, 5, 1]))

---

4. 시간 및 공간 복잡도

항목	복잡도
최선	O(n log n)
평균	O(n log n)
최악	O(n log n)
공간 복잡도	O(1) (in-place 정렬)

재귀 heapify의 경우 스택 사용으로 인해 로그 수준의 공간이 사용된다.

---

5. 특징 및 장단점

항목	설명
안정 정렬 여부	X (동일 값의 순서 보장 X)
메모리 사용	적음 (추가 공간 필요 없음)
정렬 속도	일관된 O(n log n)
정렬 기준	최대 힙 → 오름차순 / 최소 힙 → 내림차순
재귀 깊이	O(log n) (heapify 호출 시)

일관된 성능이 필요한 환경에 유리하나, 병합/퀵 정렬보다 느릴 수 있음.

---

6. 시각적 예시 (예: [4, 10, 3, 5, 1])

• 초기 배열을 최대 힙으로 구성 → [10, 5, 3, 4, 1]
• 10과 마지막 교환 → [1, 5, 3, 4, 10]
• 다시 힙 구성 및 반복 → 정렬 완료: [1, 3, 4, 5, 10]

---

7. 다른 정렬 알고리즘과 비교

알고리즘	시간 복잡도	공간 복잡도	안정성	특징
힙 정렬	O(n log n)	O(1)	X	메모리 효율적, 일정한 성능
퀵 정렬	O(n log n) 평균	O(log n)	X	평균 빠름, 최악 O(n²)
병합 정렬	O(n log n)	O(n)	O	안정적, 예측 가능
삽입 정렬	O(n²)	O(1)	O	소규모 데이터에 적합

---

8. 활용 사례

분야	활용 예시
우선순위 정렬	최대값/최솟값을 빠르게 꺼내야 하는 경우
실시간 처리	우선순위 큐 기반 처리 시스템 (ex. 스케줄러)
대규모 정렬	메모리 효율이 중요한 정렬 환경
알고리즘 문제풀이	k번째 원소, 최소 힙 활용 등

내부 정렬(in-place sort)이 필요한 환경에서 유용하다.

---

9. 결론

힙 정렬은 힙 구조를 활용해 일관된 O(n log n) 성능을 보장하는 강력한 비교 정렬 알고리즘이다. 비록 안정 정렬은 아니지만, 메모리 사용이 적고 정렬 성능이 예측 가능하다는 장점 덕분에 우선순위 기반 문제 해결이나 메모리 제약 환경에서 널리 활용된다. 다양한 정렬 알고리즘 중 효율성과 안정성을 적절히 조합해 선택할 수 있도록 학습해두어야 할 핵심 알고리즘이다.