heap이란 무엇이며, 어떻게 priority queue를 구현하나요?

Question

Accepted Answer

**binary heap(이진 힙)**은 array에 저장된 완전 이진 트리로, **힙 속성(heap property)**을 유지합니다. **min-heap**에서는 모든 부모가 자식 이하이므로 **최솟값이 항상 루트**에 있습니다. 이것이 **priority queue(우선순위 큐)**의 표준 구현입니다.

## array 레이아웃

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## 연산

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — 위로 올림(bubble up)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # min peek -> O(1)
heapq.heappop(h)       # O(log n) — 루트 제거, 아래로 내림(sift down) -> 1
```

## 복잡도

| 연산 | 시간 |
|---|---|
| min/max peek | O(1) |
| push(삽입) | O(log n) |
| pop(추출) | O(log n) |
| n개 항목으로 heap 구축 | O(n) |

## 언제 사용할까

- **우선순위에 따른 스케줄링**(예: OS 작업 스케줄러).
- **Dijkstra / Prim** 최단 경로 및 MST 알고리즘.
- **Top-K** 문제와 스트리밍 중앙값.
- **Heap sort**(제자리 O(n log n)).

## 왜 중요한가

heap은 전체를 완전히 정렬해 두지 않고도 다음으로 가장 중요한 항목을 즉시 제공하며, 이는 다시 정렬하는 것보다 훨씬 저렴합니다.

우선순위 기반 알고리즘의 근간이며, "k개의 가장 큰/작은" 질문에 자주 쓰이는 면접 도구입니다.

연산	시간
min/max peek	O(1)
push(삽입)	O(log n)
pop(추출)	O(log n)
n개 항목으로 heap 구축	O(n)