> [!abstract] Introduction
> 힙(*Heap*)은 **완전 이진 트리**[^complete-binary-tree] 구조를 만족하면서, 부모 노드의 키가 자식 노드의 키보다 항상 작거나 같은(최소 힙) 또는 크거나 같은(최대 힙) **힙 속성**을 유지하는 자료구조입니다. [[Priority Queue]]의 가장 대표적인 구현이며, [[A*]], [[Uniform-Cost Search]], Dijkstra 알고리즘, 힙 정렬 등 "가장 좋은 것을 빠르게 꺼내야 하는" 알고리즘의 핵심 엔진입니다. 이 글에서는 힙 속성의 정의, 배열 표현, 삽입·삭제 등 핵심 연산의 동작 원리와 시간 복잡도, 그리고 Python `heapq` 모듈을 살펴봅니다.
## 힙 속성
힙에는 두 가지 변형이 있다.
- **최소 힙**(*min-heap*): 모든 노드 $i$에 대해 $A[\text{parent}(i)] \le A[i]$. 루트가 항상 최솟값이다.
- **최대 힙**(*max-heap*): 모든 노드 $i$에 대해 $A[\text{parent}(i)] \ge A[i]$. 루트가 항상 최댓값이다.
이 글에서는 [[Priority Queue]]에서 가장 흔히 쓰이는 **최소 힙**을 기준으로 설명한다. 최대 힙은 비교 방향만 반대로 하면 된다.
## 배열 표현
![[heapTree.svg]]
힙은 완전 이진 트리이므로, 포인터 없이 **1차원 배열**만으로 표현할 수 있다. 인덱스가 $i$인 노드의 부모와 자식은 단순한 산술 연산으로 구한다 (1-based 인덱스 기준).
$\text{parent}(i) = \lfloor i/2 \rfloor, \quad \text{left}(i) = 2i, \quad \text{right}(i) = 2i + 1$
예를 들어, 배열 `[_, 1, 3, 5, 7, 9, 8, 10]` (인덱스 0은 사용하지 않음)은 루트가 1이고, 루트의 왼쪽 자식이 3, 오른쪽 자식이 5인 최소 힙을 나타낸다. 이 배열 표현 덕분에 추가적인 메모리 할당 없이 인덱스 계산만으로 트리를 탐색할 수 있다.
## 핵심 연산
### Sift-Up (위로 올리기)
새 원소를 삽입한 뒤, 힙 속성을 복원하는 연산이다. 삽입된 원소를 부모와 비교하며 부모보다 작으면 교환하고, 루트에 도달하거나 부모가 더 작을 때까지 반복한다.
```python
def _sift_up(self, i: int):
while i > 1 and self._data[i] < self._data[i // 2]:
self._data[i], self._data[i // 2] = self._data[i // 2], self._data[i]
i //= 2
```
트리의 높이만큼 올라가므로 $O(\log n)$이다.
### Sift-Down (아래로 내리기)
루트에서 원소를 꺼낸 뒤, 힙 속성을 복원하는 연산이다. 현재 노드를 두 자식 중 더 작은 쪽과 비교하여, 자식이 더 작으면 교환하고 아래로 내려간다.
```python
def _sift_down(self, i: int):
while 2 * i <= self._size:
child = 2 * i
# 오른쪽 자식이 존재하고 더 작으면 오른쪽 선택
if child + 1 <= self._size and self._data[child + 1] < self._data[child]:
child += 1
if self._data[i] <= self._data[child]:
break
self._data[i], self._data[child] = self._data[child], self._data[i]
i = child
```
역시 트리의 높이만큼 내려가므로 $O(\log n)$이다.
### Insert (삽입)
배열 끝에 원소를 추가한 뒤 sift-up을 수행한다. $O(\log n)$.
### Extract-Min (최솟값 추출)
루트(최솟값)를 꺼내고, 배열의 마지막 원소를 루트에 놓은 뒤 sift-down을 수행한다. $O(\log n)$.
### Peek (확인)
루트를 꺼내지 않고 반환한다. 배열의 첫 번째 원소를 읽기만 하면 되므로 $O(1)$.
## 시간 복잡도
| 연산 | 시간 복잡도 |
| -------------- | ----------- |
| `insert` | $O(\log n)$ |
| `extract-min` | $O(\log n)$ |
| `peek` | $O(1)$ |
| `decrease-key` | $O(\log n)$ |
| `build-heap` | $O(n)$ |
`build-heap`이 $O(n \log n)$이 아닌 $O(n)$인 이유가 주목할 만하다. 배열의 뒤쪽 절반은 리프 노드이므로 sift-down이 필요 없고, 위쪽으로 갈수록 노드 수는 줄어들지만 sift-down 깊이는 늘어난다. 이 두 요소의 합이 기하급수적으로 수렴하여 전체 비용이 $O(n)$이 되는 것이다[^build-heap-proof].
## Python 구현
```python
class MinHeap:
"""1-based 인덱스 최소 힙."""
def __init__(self):
self._data = [None] # 인덱스 0은 사용하지 않음
self._size = 0
def insert(self, key):
self._data.append(key)
self._size += 1
self._sift_up(self._size)
def extract_min(self):
if self._size == 0:
raise IndexError("Heap is empty")
min_val = self._data[1]
self._data[1] = self._data[self._size]
self._data.pop()
self._size -= 1
if self._size > 0:
self._sift_down(1)
return min_val
def peek(self):
if self._size == 0:
raise IndexError("Heap is empty")
return self._data[1]
def _sift_up(self, i: int):
while i > 1 and self._data[i] < self._data[i // 2]:
self._data[i], self._data[i // 2] = self._data[i // 2], self._data[i]
i //= 2
def _sift_down(self, i: int):
while 2 * i <= self._size:
child = 2 * i
if child + 1 <= self._size and self._data[child + 1] < self._data[child]:
child += 1
if self._data[i] <= self._data[child]:
break
self._data[i], self._data[child] = self._data[child], self._data[i]
i = child
```
## Python `heapq` 모듈
실무에서는 직접 힙을 구현하기보다 Python 표준 라이브러리의 `heapq` 모듈을 사용한다. `heapq`는 일반 리스트를 최소 힙으로 관리하며, 0-based 인덱스를 사용한다.
```python
import heapq
data = [5, 3, 8, 1, 9, 7, 10]
heapq.heapify(data) # O(n)에 리스트를 힙으로 변환
print(heapq.heappop(data)) # 1 — 최솟값 추출
heapq.heappush(data, 2) # 2 삽입
print(data[0]) # 2 — 현재 최솟값 확인 (peek)
```
`heapq`는 최소 힙만 지원하므로, 최대 힙이 필요하면 키의 부호를 뒤집는 트릭을 사용한다. `heappush(pq, -key)`로 삽입하고, `heappop(pq)`로 꺼낸 뒤 부호를 다시 뒤집으면 된다.
## 어디에 쓰이는가
힙은 [[Priority Queue|우선순위 큐]]의 표준 구현이므로, 우선순위 큐가 필요한 거의 모든 곳에서 힙이 쓰인다. [[A*]]과 [[Uniform-Cost Search]]에서 $f(n)$이나 $g(n)$이 가장 작은 노드를 효율적으로 꺼내는 데 사용되며, 허프만 코딩에서 빈도가 가장 낮은 두 노드를 반복적으로 합칠 때도 힙이 핵심이다. 힙 정렬(*heapsort*)은 최대 힙에서 루트를 반복 추출하여 $O(n \log n)$ 정렬을 수행하며, 추가 메모리가 $O(1)$이라는 장점이 있다.
---
## 출처
- Cormen, T. H. et al. (2022) *Introduction to Algorithms*. 4th edn. Cambridge, MA: MIT Press. Chapter 6.
- Python Software Foundation (2025) *heapq — Heap queue algorithm*. Available at: https://docs.python.org/3/library/heapq.html.
[^complete-binary-tree]: 완전 이진 트리(*complete binary tree*) — 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 빈틈없이 채워진 이진 트리. 배열 인덱스로 부모-자식 관계를 표현할 수 있어 힙의 기반 구조로 쓰인다.
[^build-heap-proof]: `build-heap`의 $O(n)$ 증명 — 높이 $h$에 있는 노드 수는 최대 $\lceil n / 2^{h+1} \rceil$이고, 각 노드의 sift-down 비용은 $O(h)$이다. 전체 비용은 $\sum_{h=0}^{\lfloor \log n \rfloor} \lceil n / 2^{h+1} \rceil \cdot O(h) = O(n \sum_{h=0}^{\infty} h / 2^h) = O(n)$이다. Cormen et al. (2022), Chapter 6.3 참조.