이진 힙이란? 우선순위 큐, 코드, 시간 복잡도

힙이 해결하는 문제

많은 프로그램이 계속 변하는 컬렉션에서 가장 급한 항목을 반복해서 꺼내야 합니다. 시뮬레이션의 다음 이벤트, 다익스트라 알고리즘에서 아직 방문하지 않은 가장 가까운 노드, 우선순위가 가장 높은 작업, 스트림에서 가장 큰 k개의 값이 그런 예입니다. 삽입할 때마다 컬렉션 전체를 정렬하면 매번 O(n log n)이 듭니다. 정렬된 리스트는 제거가 싸지만 삽입이 O(n)입니다. 힙은 삽입과 최솟값 제거를 모두 O(log n)에 처리하며, 이것이 바로 우선순위 큐에 필요한 성능입니다.

핵심 아이디어: 배열에 저장하는 트리

힙은 완전 이진 트리입니다. 마지막 레벨을 제외한 모든 레벨이 가득 차 있고, 마지막 레벨은 왼쪽부터 채워집니다. 이런 모양 덕분에 포인터 없이 평범한 리스트에 트리를 저장할 수 있습니다.

힙 속성은 두 가지 복구 연산으로 유지합니다. sift up은 새 항목을 맨 끝에 추가한 뒤, 부모보다 작은 동안 부모와 교환하는 연산입니다. sift down은 마지막 항목을 루트로 옮긴 뒤, 더 작은 자식보다 큰 동안 그 자식과 교환하는 연산입니다. 두 연산 모두 루트에서 리프까지의 경로 하나를 따라 움직이므로 교환은 많아야 약 log2(n)번입니다.

예제: push와 pop

최소 힙 [2, 5, 3, 9, 6]에서 시작합니다(2가 루트이고, 그 자식은 5와 3이며, 5의 자식은 9와 6입니다).

1. 1을 push합니다. 끝에 추가하여 [2, 5, 3, 9, 6, 1]이 됩니다. 인덱스 5의 부모는 인덱스 2(값 3)입니다.
2. 1이 3보다 작으므로 교환합니다: [2, 5, 1, 9, 6, 3]. 이제 인덱스 2의 부모는 인덱스 0(값 2)입니다.
3. 1이 2보다 작으므로 교환합니다: [1, 5, 2, 9, 6, 3]. 루트에 도달했으므로 멈춥니다.
4. pop합니다. 루트 1을 제거하고 마지막 항목 3을 루트로 옮깁니다: [3, 5, 2, 9, 6].
5. 루트의 자식은 5와 2이고 더 작은 쪽은 2입니다. 3이 더 크므로 교환합니다: [2, 5, 3, 9, 6]. 인덱스 2에는 자식이 없으므로 멈춥니다. pop은 1을 반환했습니다.

파이썬으로 구현하는 최소 힙

이 클래스는 내부 동작을 보여 줍니다. 실제 코드에서는 다음 절에서 보는 heapq를 사용하세요.

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

파이썬 heapq로 만드는 우선순위 큐

heapq 모듈은 일반 리스트에서 동작하며 항상 최소 힙을 유지합니다. heapify는 기존 리스트를 제자리에서 O(n)에 힙으로 바꿉니다. 우선순위를 쓰려면 튜플을 push하세요. 파이썬은 튜플을 요소별로 비교하므로 첫 번째 요소가 우선순위가 됩니다. 우선순위가 같은 항목끼리 직접 비교하는 일이 없도록 동점 처리용 카운터를 추가하세요.

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

최대 힙을 위해 파이썬 3.14에 heapq.heapify_max, heapq.heappush_max, heapq.heappop_max가 추가되었습니다. 이전 버전에서는 키의 부호를 바꿔 heapq.heappush(h, -score)처럼 push하고 pop할 때 다시 부호를 바꾸는 방법을 흔히 씁니다.

시간 복잡도와 공간 복잡도

push를 n번 호출해서 힙을 만들면 O(n log n)이 듭니다. heapify는 마지막 부모부터 루트까지 sift down을 하며 O(n)이므로, 항목을 이미 모두 가지고 있다면 이쪽을 쓰세요.

변형과 흔한 실수

• 최대 힙: 같은 코드에서 비교만 뒤집은 것입니다. 파이썬에서는 _max 함수(3.14 이상)를 쓰거나 키의 부호를 바꿉니다.
• d-ary 힙: 각 노드가 자식을 d개 가집니다. 트리가 얕아져 push는 더 싸지고 pop은 약간 더 비쌉니다.
• 인덱스 우선순위 큐 / decrease-key: heapq는 항목의 우선순위를 제자리에서 바꿀 수 없습니다. (다익스트라 알고리즘에서 쓰는) 일반적인 우회책은 새 항목을 push하고, pop될 때 오래된 항목을 건너뛰는 것입니다.
• 비교할 수 없는 항목을 비교하는 실수: (priority, dict)를 push하면 두 우선순위가 같을 때 파이썬이 dict끼리 비교하려 하므로 TypeError가 발생합니다. 튜플의 두 번째 요소로 카운터를 추가하세요.
• 힙 리스트가 정렬되어 있다고 착각하는 실수. 보장되는 것은 heap[0]뿐입니다. 전체를 순서대로 보려면 sorted(heap)을 쓰세요.
• 교재의 1부터 시작하는 공식(자식이 2i와 2i + 1)을 0부터 시작하는 파이썬 리스트에 섞어 써서 생기는 off-by-one 오류.

힙을 쓸 때와 대표 문제

계속 변하는 컬렉션에서 가장 작거나 가장 큰 항목만 반복해서 필요할 때 힙을 사용하세요. 정렬된 순회나 임의 삭제도 필요하면 정렬된 리스트나 균형 트리를 쓰고, 최솟값이 한 번만 필요하면 그냥 min()을 쓰세요.

대표적인 활용: 다익스트라 최단 경로와 프림 최소 신장 트리, k개의 정렬된 리스트 병합(heapq.merge), 가장 큰(또는 작은) k개 찾기(크기 k의 힙 유지, O(n log k)), 이동 중앙값(힙 두 개), 작업 스케줄러와 이벤트 기반 시뮬레이션, 힙 정렬.