힙 — 우선순위 큐의 원리

이 토픽을 마치면

힙의 구조와 동작 원리를 설명할 수 있고, Python의 heapq로 우선순위 큐를 구현하여 "가장 작은(또는 큰) 값을 빠르게 꺼내는" 문제를 풀 수 있습니다.

문제 — "가장 급한 것"을 빠르게 꺼내기

병원 응급실을 생각해보세요. 환자가 도착한 순서(큐)가 아니라 증상의 심각도에 따라 치료 순서가 바뀝니다. 이런 "우선순위가 있는 큐"를 구현하려면 어떻게 해야 할까요?

정렬된 리스트: 삽입할 때마다 정렬 → O(n)
정렬 안 된 리스트: 최솟값을 찾을 때 전수 조사 → O(n)

힙은 삽입과 최솟값 추출 모두 **O(log n)**으로 처리합니다.

힙의 규칙

최소 힙(Min Heap)의 규칙은 단순합니다:

부모는 항상 자식보다 작거나 같다

text

1          ← 최솟값은 항상 루트
       / \
      3   5
     / \ / \
    7  4 8  6

루트에 항상 가장 작은 값이 있으므로, 최솟값을 O(1)에 확인할 수 있습니다.

BST와 다른 점: BST는 "왼쪽 < 부모 < 오른쪽"이지만, 힙은 "부모 < 자식들"만 지킵니다. 형제 간 순서는 상관없습니다.

배열로 표현하기

힙은 트리지만 실제로는 배열로 저장합니다:

text

인덱스:  [0, 1, 2, 3, 4, 5, 6]
값:      [1, 3, 5, 7, 4, 8, 6]

text

부모 인덱스 i에 대해:
  왼쪽 자식 = 2*i + 1
  오른쪽 자식 = 2*i + 2
  부모 = (i - 1) // 2

인덱스 0의 자식: 1, 2 / 인덱스 1의 자식: 3, 4 / 인덱스 2의 자식: 5, 6. 포인터 없이 인덱스 계산만으로 부모-자식 관계를 알 수 있습니다.

삽입과 삭제의 원리

삽입 (heappush): 배열 끝에 추가하고, 부모와 비교하면서 위로 올립니다 (sift up):

text

초기:  [1, 3, 5, 7, 4, 8, 6]
2 삽입: [1, 3, 5, 7, 4, 8, 6, 2]
       ↑ 인덱스 7의 부모(3) = 인덱스 3(값 7)
       2 < 7 → 교환: [1, 3, 5, 2, 4, 8, 6, 7]
       ↑ 인덱스 3의 부모 = 인덱스 1(값 3)
       2 < 3 → 교환: [1, 2, 5, 3, 4, 8, 6, 7]
       ↑ 인덱스 1의 부모 = 인덱스 0(값 1)
       2 > 1 → 정지

삭제 (heappop): 루트를 제거하고 마지막 원소를 루트에 놓은 뒤, 자식과 비교하면서 아래로 내립니다 (sift down). 두 연산 모두 트리 높이만큼만 이동하므로 O(log n)입니다.

Python heapq

Python은 heapq 모듈로 최소 힙을 제공합니다:

python

import heapq

# 빈 리스트를 힙으로 사용
heap = []

# 삽입 — O(log n)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)

print(heap)        # [1, 3, 7, 5] — 내부 순서는 힙 규칙대로
print(heap[0])     # 1 — 최솟값은 항상 인덱스 0

# 최솟값 추출 — O(log n)
smallest = heapq.heappop(heap)
print(smallest)    # 1
print(heap)        # [3, 5, 7]

heappush와 heappop만 기억하면 됩니다.

기존 리스트를 힙으로 변환

python

data = [9, 1, 4, 7, 2, 8, 3]
heapq.heapify(data)  # O(n) — 정렬(O(n log n))보다 빠름
print(data)          # [1, 2, 3, 7, 9, 8, 4]

heapify는 리스트를 제자리(in-place)에서 힙으로 만듭니다.

우선순위 큐 구현

python

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, priority, item):
        heapq.heappush(self.heap, (priority, item))
    
    def pop(self):
        return heapq.heappop(self.heap)[1]
    
    def is_empty(self):
        return len(self.heap) == 0

# 응급실 예시
er = PriorityQueue()
er.push(3, "감기 환자")
er.push(1, "심정지 환자")    # 우선순위 1이 가장 급함
er.push(2, "골절 환자")

print(er.pop())  # "심정지 환자"
print(er.pop())  # "골절 환자"
print(er.pop())  # "감기 환자"

튜플의 첫 번째 요소가 비교 기준이 됩니다. 숫자가 작을수록 우선순위가 높습니다.

최대 힙이 필요할 때

Python의 heapq는 최소 힙만 제공합니다. 최대 힙이 필요하면 값을 음수로 넣습니다:

python

# 최대 힙 효과
max_heap = []
for val in [3, 1, 5, 2, 4]:
    heapq.heappush(max_heap, -val)

print(-heapq.heappop(max_heap))  # 5 (가장 큰 값)
print(-heapq.heappop(max_heap))  # 4

유용한 함수들

python

data = [7, 3, 9, 1, 5, 8, 2]

# 가장 작은 3개
print(heapq.nsmallest(3, data))  # [1, 2, 3]

# 가장 큰 3개
print(heapq.nlargest(3, data))   # [9, 8, 7]

# 정렬된 여러 리스트를 하나로 병합
a = [1, 4, 7]
b = [2, 5, 8]
c = [3, 6, 9]
print(list(heapq.merge(a, b, c)))  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도 정리

연산	시간 복잡도
삽입 (heappush)	O(log n)
최솟값 추출 (heappop)	O(log n)
최솟값 확인 (heap[0])	O(1)
힙 구성 (heapify)	O(n)

목적	자료구조
정확한 키로 검색	해시 테이블
정렬된 순서 유지	BST
최솟값/최댓값만 빠르게	힙

힙 정렬

힙을 이용해 정렬할 수 있습니다:

python

def heap_sort(arr):
    heapq.heapify(arr)  # O(n)
    return [heapq.heappop(arr) for _ in range(len(arr))]

data = [7, 3, 9, 1, 5]
print(heap_sort(data))  # [1, 3, 5, 7, 9]

시간 복잡도 O(n log n)으로 퀵 정렬, 병합 정렬과 동급입니다. 실무에서는 Python의 sorted()(Timsort)가 더 빠르지만, 개념적으로 힙 정렬의 원리를 이해하는 것이 중요합니다.

실전 — Top K 문제

"100만 개의 데이터에서 가장 큰 10개"를 구하는 문제:

python

import heapq

data = [random.randint(0, 1_000_000) for _ in range(1_000_000)]

# ❌ 전체 정렬 — O(n log n)
top10_sort = sorted(data, reverse=True)[:10]

# ✅ 힙 사용 — O(n log k)
top10_heap = heapq.nlargest(10, data)

전체를 정렬하면 O(n log n)이지만, 힙은 크기 k만 유지하므로 O(n log k)입니다. k가 n보다 훨씬 작을 때 큰 차이가 납니다.

python

# 직접 구현하면 원리가 보입니다
min_heap = []
for val in data:
    if len(min_heap) < 10:
        heapq.heappush(min_heap, val)
    elif val > min_heap[0]:
        heapq.heapreplace(min_heap, val)

top10 = sorted(min_heap, reverse=True)

크기 10의 최소 힙을 유지합니다. 새 값이 힙의 최솟값보다 크면 교체합니다. 마지막에 남은 10개가 전체에서 가장 큰 10개입니다.

실전 — 다익스트라 알고리즘

최단 경로 알고리즘인 다익스트라도 힙을 사용합니다:

python

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))
    return dist

"아직 방문하지 않은 노드 중 가장 가까운 것"을 매번 꺼내야 하므로, 힙이 없으면 O(V²), 힙을 쓰면 O((V+E) log V)로 동작합니다.

힙은 "전체를 정렬할 필요는 없고, 가장 중요한 것 하나만 빠르게 꺼내면 되는" 상황에 최적입니다.