힙 정렬(Heap Sort): 우선순위 기반 정렬 알고리즘

IT이야기

힙 정렬(Heap Sort): 우선순위 기반 정렬 알고리즘

Chiba-in 2025. 3. 2. 06:30

🔹 힙 정렬이란?

1. 힙 정렬(Heap Sort)의 정의

**힙 정렬(Heap Sort)**은 힙(Heap) 자료구조를 활용하여 데이터를 정렬하는 효율적인 알고리즘입니다. 힙 정렬은 이진 힙(Binary Heap)을 사용하여 최대값(또는 최소값)을 반복적으로 추출하고, 배열을 정렬하는 방식으로 동작합니다.

✅ 힙 정렬의 주요 특징:

완전 이진 트리(Complete Binary Tree) 기반의 힙을 활용
최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 사용하여 정렬 수행
O(n log n)의 시간 복잡도를 보장
제자리 정렬(In-Place Sort)로 추가적인 메모리 사용이 적음
불안정 정렬(Unstable Sort), 즉 동일한 값의 상대적인 순서를 유지하지 않음

📌 힙 정렬은 대량의 데이터를 정렬할 때 안정적인 성능을 제공하는 알고리즘입니다.

🔹 힙 정렬의 동작 과정

주어진 배열을 힙(Heap) 자료구조로 변환 (Heapify 과정)
힙의 루트 노드(최댓값 또는 최솟값)를 제거하여 정렬된 배열로 이동
남은 요소로 다시 힙을 구성하여 위 과정을 반복

✔️ 힙 정렬 예제 (Python):

import heapq

def heap_sort(arr):
    heapq.heapify(arr)  # 배열을 최소 힙으로 변환
    sorted_arr = [heapq.heappop(arr) for _ in range(len(arr))]
    return sorted_arr

arr = [64, 34, 25, 12, 22, 11, 90]
print(heap_sort(arr))  # 출력: [11, 12, 22, 25, 34, 64, 90]

📌 Python의 **`` 모듈을 사용하면 최소 힙을 쉽게 구현할 수 있습니다.**

🔹 힙 정렬의 시간 복잡도 분석

케이스	시간 복잡도
최악의 경우 (O(n log n))	모든 경우에서 일정한 성능 보장
평균적인 경우 (O(n log n))	일반적인 무작위 데이터 정렬
최선의 경우 (O(n log n))	이미 정렬된 경우에도 O(n log n)

📌 퀵 정렬과 달리 최악의 경우에도 O(n log n)을 유지하여 안정적인 성능을 보장합니다.

🔹 힙 정렬의 시각적 표현

✔️ 입력 배열: [5, 3, 8, 4, 2]

배열을 최대 힙(Max Heap)으로 변환:
```
    8
   / \
  5   3
 / \
4   2
```
최댓값(루트) 제거 후 힙 재구성:
```
    5
   / \
  4   3
 /
2
```
반복하여 최댓값을 정렬된 배열로 이동
```
[2, 3, 4, 5, 8] (정렬 완료)
```

📌 힙 정렬은 힙을 유지하며 정렬을 수행하는 방식으로 동작합니다.

🔹 힙 정렬의 장점과 단점

✅ 장점:

O(n log n)의 일정한 시간 복잡도를 유지
제자리 정렬(In-Place Sort)로 추가 메모리 사용이 적음
퀵 정렬과 달리 최악의 경우에도 O(n log n) 보장
우선순위 큐(Priority Queue) 기반의 정렬 방식으로 활용 가능

❌ 단점:

정렬된 데이터를 입력하면 성능이 떨어질 수 있음
불안정 정렬(Unstable Sort), 즉 동일한 값의 상대적 순서가 변경될 수 있음
캐시 친화적이지 않아 퀵 정렬보다 실제 성능이 떨어질 수 있음

📌 힙 정렬은 안정적인 성능을 보장하지만, 실제 성능은 퀵 정렬보다 다소 낮을 수 있습니다.

🔹 힙 정렬 vs 다른 정렬 알고리즘 비교

정렬 알고리즘	최악 시간 복잡도	평균 시간 복잡도	공간 복잡도	안정 정렬
버블 정렬	O(n²)	O(n²)	O(1)	O
선택 정렬	O(n²)	O(n²)	O(1)	X
삽입 정렬	O(n²)	O(n²)	O(1)	O
병합 정렬	O(n log n)	O(n log n)	O(n)	O
퀵 정렬	O(n²)	O(n log n)	O(log n)	X
힙 정렬	O(n log n)	O(n log n)	O(1)	X

📌 힙 정렬은 일정한 O(n log n) 성능을 보장하지만, 퀵 정렬보다 실질적인 성능이 떨어질 수 있습니다.

📌 결론

✅ 힙 정렬(Heap Sort)은 힙 자료구조를 활용하여 데이터를 효율적으로 정렬하는 알고리즘입니다. ✅ O(n log n)의 일정한 성능을 보장하며, 최악의 경우에도 안정적인 정렬이 가능합니다. ✅ 추가적인 메모리 사용이 적지만, 불안정 정렬이며 실제 성능은 퀵 정렬보다 떨어질 수 있습니다. ✅ 우선순위 큐와 함께 활용하면 높은 효율성을 발휘할 수 있습니다.