heap sort는 어떻게 동작하나요?

Question

Accepted Answer

**Heap sort**는 배열로부터 **binary heap(이진 힙)**을 만든 뒤, 최댓값을 반복적으로 추출하여 정렬된 순서를 만들어 냅니다. **O(n log n)**으로 동작하며 **제자리 정렬**입니다.

## 개념

max-heap은 가장 큰 원소를 루트에 유지합니다. 힙을 만들고(O(n)), 루트를 끝으로 교환하고, 힙을 줄이고, 다시 힙으로 만드는(sift down) 작업을 n번 수행합니다.

## 예시

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # O(n)에 min-heap 생성
    return [heapq.heappop(arr)       # 가장 작은 값을 n번 꺼냄
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

전형적인 구현은 배열 내에서 sift down하여 제자리로 수행합니다.

## 복잡도

- **시간:** 모든 경우에 O(n log n). **공간:** 제자리 O(1).

## 언제 사용하나 / 함정

**보장된 O(n log n)** *그리고* **O(1) 추가 메모리**가 필요할 때 사용하세요(merge sort는 O(n)이 필요하고 quicksort는 O(n²) 위험이 있습니다). 안정 정렬이 **아니며** 캐시 지역성이 나빠서 실제로는 quicksort보다 느린 경우가 많습니다. 같은 힙이 **priority queue(우선순위 큐)**와 top-k 원소 찾기를 뒷받침합니다.

## 왜 중요한가

Heap sort는 최악의 경우 O(n log n)이면서 제자리 정렬인 유일한 흔한 정렬로, 메모리가 제약된 환경이나 보장된 한계가 필요한 환경에서 유용합니다.

그 아래의 힙 구조는 폭넓게 유용합니다 — priority queue, Dijkstra 알고리즘, 스트리밍 top-k.

올바른 자료구조가 알고리즘을 효율적으로 만든다는 점을 확고히 합니다.