Heap

힙 속성

힙에는 두 가지 변형이 있다.

• 최소 힙(min-heap): 모든 노드 $i$에 대해 $A[\text{parent}(i)] \le A[i]$. 루트가 항상 최솟값이다.
• 최대 힙(max-heap): 모든 노드 $i$에 대해 $A[\text{parent}(i)] \ge A[i]$. 루트가 항상 최댓값이다.

이 글에서는 Priority Queue에서 가장 흔히 쓰이는 최소 힙을 기준으로 설명한다. 최대 힙은 비교 방향만 반대로 하면 된다.

배열 표현

힙은 완전 이진 트리이므로, 포인터 없이 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 (위로 올리기)

새 원소를 삽입한 뒤, 힙 속성을 복원하는 연산이다. 삽입된 원소를 부모와 비교하며 부모보다 작으면 교환하고, 루트에 도달하거나 부모가 더 작을 때까지 반복한다.

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 (아래로 내리기)

루트에서 원소를 꺼낸 뒤, 힙 속성을 복원하는 연산이다. 현재 노드를 두 자식 중 더 작은 쪽과 비교하여, 자식이 더 작으면 교환하고 아래로 내려간다.

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)$.

시간 복잡도

build-heap이 $O(n \log n)$이 아닌 $O(n)$인 이유가 주목할 만하다. 배열의 뒤쪽 절반은 리프 노드이므로 sift-down이 필요 없고, 위쪽으로 갈수록 노드 수는 줄어들지만 sift-down 깊이는 늘어난다. 이 두 요소의 합이 기하급수적으로 수렴하여 전체 비용이 $O(n)$이 되는 것이다².

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 인덱스를 사용한다.

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)로 꺼낸 뒤 부호를 다시 뒤집으면 된다.

어디에 쓰이는가

힙은 우선순위 큐의 표준 구현이므로, 우선순위 큐가 필요한 거의 모든 곳에서 힙이 쓰인다. 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.

Footnotes

1. 완전 이진 트리(complete binary tree) — 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 빈틈없이 채워진 이진 트리. 배열 인덱스로 부모-자식 관계를 표현할 수 있어 힙의 기반 구조로 쓰인다. ↩

2. 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 참조. ↩