완전 이진 트리·힙·우선순위 큐

병원 응급실은 도착한 순서가 아니라 위급한 순서로 환자를 봅니다. 새 환자는 계속 도착하고, 의사가 비면 그때 대기 중인 환자 가운데 가장 위급한 사람을 부릅니다. 이처럼 값을 넣는 일과 우선순위가 가장 높은 값을 꺼내는 일이 섞여서 반복될 때 쓰는 자료구조를 우선순위 큐(priority queue)라고 합니다. 이 글에서는 우선순위 큐를 효율적으로 만드는 대표적인 방법인 힙(heap)을 직접 구현하고, 힙이 왜 넣기와 꺼내기를 모두 O(log n)에 할 수 있는지 설명합니다. 힙은 다음 글의 힙 정렬과 8장의 최단 경로 알고리즘에서 다시 쓰입니다.

우선순위 큐가 해야 하는 일

우선순위 큐는 세 가지 작업을 제공합니다. 값을 넣는 작업, 우선순위가 가장 높은 값을 꺼내는 작업, 꺼내지 않고 확인만 하는 작업입니다. 여기서는 값이 클수록 우선순위가 높다고 하겠습니다. 이 작업들을 이미 아는 방법으로 만들면 어느 한쪽이 느려집니다.

정렬하지 않은 리스트는 꺼낼 때마다 최댓값을 찾아야 하고, 정렬해 둔 리스트는 넣을 때마다 삽입 정렬처럼 값들을 밀어야 합니다. 넣기와 꺼내기를 n번씩 섞어 하면 둘 다 O(n²)이 듭니다. 힙은 리스트를 완전히 정렬하지 않고 "가장 큰 값이 맨 앞에 있다"는 데 필요한 만큼만 순서를 유지해서, 두 작업을 모두 O(log n)에 해냅니다.

완전 이진 트리를 리스트에 담기

힙을 이해하려면 먼저 트리(tree)라는 구조가 필요합니다. 트리의 정확한 정의와 성질은 이산수학의 트리와 이진 트리의 구조에서 다루고, 여기서는 힙에 필요한 만큼만 살펴봅니다. 트리는 노드(node)들이 부모와 자식 관계로 이어진 구조입니다. 맨 위의 부모가 없는 노드를 루트(root), 자식이 없는 노드를 리프(leaf)라고 합니다. 모든 노드의 자식이 많아야 둘인 트리를 이진 트리(binary tree)라 하고, 두 자식을 왼쪽 자식과 오른쪽 자식으로 구분합니다.

이진 트리 가운데 마지막 층을 뺀 모든 층이 꽉 차 있고, 마지막 층은 왼쪽부터 빈틈없이 채운 것을 완전 이진 트리(complete binary tree)라고 합니다. 이 모양은 리스트에 담기가 아주 쉽습니다. 루트부터 층마다 왼쪽에서 오른쪽으로 번호를 붙여 리스트에 차례로 넣으면, 인덱스 i인 노드의 왼쪽 자식은 2i + 1, 오른쪽 자식은 2i + 2, 부모는 (i - 1) // 2에 있습니다. 자식의 인덱스가 리스트 길이 이상이면 그 자식은 없는 것입니다. 노드끼리 연결 정보를 따로 저장할 필요 없이 인덱스 계산만으로 부모와 자식을 찾을 수 있습니다.

그림의 리스트 [9, 7, 8, 2, 3, 4, 6]에서 루트는 인덱스 0의 9이고, 그 자식은 인덱스 1의 7과 인덱스 2의 8입니다. 7의 자식은 인덱스 3과 4의 2와 3, 8의 자식은 인덱스 5와 6의 4와 6입니다. 인덱스 3부터 6까지는 자식의 인덱스가 7 이상이라 리프입니다.

이 식이 맞는 이유는 층마다 노드 수가 두 배로 늘기 때문입니다. 층 k에는 노드가 2ᵏ개 있고, 그 층은 인덱스 2ᵏ - 1부터 시작합니다. 층 k에서 j번째 노드의 인덱스가 i = 2ᵏ - 1 + j라면, 그 왼쪽에 있는 같은 층의 노드 j개가 각각 자식을 둘씩 가지므로 이 노드의 왼쪽 자식은 다음 층의 2j번째, 곧 인덱스 2ᵏ⁺¹ - 1 + 2j = 2i + 1입니다. 또 완전 이진 트리는 층이 꽉 차며 내려가므로, 노드가 n개일 때 루트에서 리프까지 내려가는 높이는 ⌊log₂ n⌋입니다.

힙 조건

최대 힙(max heap)은 모든 부모의 값이 자식의 값보다 작지 않은 완전 이진 트리입니다. 이 조건은 부모와 자식 사이에만 정해져 있지만, 루트에서 어떤 노드까지 내려가는 길을 따라가면 값이 커지는 일이 없으므로 루트가 전체의 최댓값이 됩니다. 반대로 모든 부모가 자식보다 크지 않으면 최소 힙(min heap)이고, 루트가 최솟값입니다.

힙은 정렬된 리스트가 아니라는 점에 주의해야 합니다. [9, 7, 8, 2, 3, 4, 6]은 최대 힙이지만 내림차순이 아닙니다. 형제인 7과 8 사이에는 아무 조건이 없고, 7의 자식 3이 8의 자식 4보다 작다는 것도 힙 조건과는 상관이 없습니다. 힙이 보장하는 것은 루트가 최댓값이라는 사실 하나뿐이고, 그 덕분에 정렬보다 적은 일로 그 사실을 유지할 수 있습니다.

넣을 때는 위로 올린다

새 값을 넣을 때는 먼저 리스트 끝에 붙입니다. 그러면 마지막 층의 다음 빈자리가 채워지므로 완전 이진 트리의 모양은 그대로입니다. 하지만 새 값이 부모보다 크면 힙 조건이 깨집니다. 이때 새 값과 부모를 맞바꾸고, 올라간 자리에서 다시 부모와 비교하기를 부모가 더 크거나 루트에 도착할 때까지 되풀이합니다. 이것을 위로 올리기(sift-up)라고 합니다.

[9, 7, 8]에 10을 넣으면 [9, 7, 8, 10]이 되고, 인덱스 3의 부모는 인덱스 1의 7입니다. 10이 더 크므로 맞바꾸어 [9, 10, 8, 7], 다시 인덱스 1의 부모인 인덱스 0의 9와 비교해 맞바꾸어 [10, 9, 8, 7]이 됩니다. 루트에 도착했으므로 멈춥니다. 맞바꿀 때마다 한 층씩 올라가므로 많아야 높이만큼, 곧 O(log n)번 맞바꿉니다.

꺼낼 때는 아래로 내린다

최댓값은 루트에 있으므로 확인은 O(1)입니다. 꺼낼 때는 루트를 돌려주고 그 자리를 채워야 하는데, 완전 이진 트리의 모양을 지키려면 리스트의 마지막 값을 루트로 옮기는 것이 가장 간단합니다. 마지막 칸이 비면서 모양은 유지되지만, 루트로 옮긴 값은 대개 작은 값이라 힙 조건이 깨집니다.

그래서 루트에서부터 아래로 내려가며 고칩니다. 현재 값이 두 자식 가운데 큰 쪽보다 작으면 그 큰 자식과 맞바꾸고, 내려간 자리에서 같은 일을 되풀이합니다. 자식이 없거나 현재 값이 두 자식보다 작지 않으면 멈춥니다. 이것을 아래로 내리기(sift-down)라고 합니다. 두 자식 가운데 큰 쪽과 바꾸는 이유는, 그래야 새로 부모가 된 값이 다른 자식보다도 작지 않아 그 자리의 힙 조건이 지켜지기 때문입니다.

[10, 9, 8, 7]에서 꺼내면 10을 돌려주고 마지막 값 7을 루트로 옮겨 [7, 9, 8]이 됩니다. 7의 자식 9와 8 가운데 큰 9와 맞바꾸어 [9, 7, 8]이 되고, 인덱스 1의 7은 자식이 없으므로 멈춥니다. 내려갈 때도 한 번에 한 층씩이므로 O(log n)입니다.

한꺼번에 힙 만들기

이미 있는 리스트 전체를 힙으로 만들 때는 값을 하나씩 넣는 대신 아래에서부터 고치는 방법이 더 빠릅니다. 리프는 자식이 없어 그 자체로 힙이므로, 자식이 있는 마지막 노드인 인덱스 n // 2 - 1부터 루트까지 거꾸로 가면서 각 노드에 아래로 내리기를 합니다. 어떤 노드를 고칠 때는 그 아래의 두 부분이 이미 힙이므로, 그 노드의 값 하나만 알맞은 자리로 내리면 그 노드 아래 전체가 힙이 됩니다.

아래 코드는 지금까지의 작업을 모두 구현합니다. sift_down의 size는 힙으로 쓰는 앞부분의 길이로, 다음 글의 힙 정렬에서 쓰려고 따로 받게 했습니다. max_heap_push와 max_heap_pop은 넘겨받은 리스트를 직접 바꿉니다.

def sift_down(values, root, size):
    while 2 * root + 1 < size:
        child = 2 * root + 1
        if child + 1 < size and values[child + 1] > values[child]:
            child += 1
        if values[root] >= values[child]:
            return
        values[root], values[child] = values[child], values[root]
        root = child


def build_max_heap(values):
    result = list(values)
    for root in range(len(result) // 2 - 1, -1, -1):
        sift_down(result, root, len(result))
    return result


def max_heap_push(heap, value):
    heap.append(value)
    child = len(heap) - 1
    while child > 0:
        parent = (child - 1) // 2
        if heap[parent] >= heap[child]:
            break
        heap[parent], heap[child] = heap[child], heap[parent]
        child = parent


def max_heap_pop(heap):
    if not heap:
        raise IndexError("빈 힙에서는 꺼낼 수 없습니다")
    maximum = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0, len(heap))
    return maximum


def is_max_heap(values):
    return all(values[(i - 1) // 2] >= values[i] for i in range(1, len(values)))


heap = build_max_heap([2, 7, 4, 9, 3, 8, 6])
print(heap, is_max_heap(heap))
small = [9, 7, 8]
max_heap_push(small, 10)
print(small)
print(max_heap_pop(small), small)
print([max_heap_pop(heap) for _ in range(len(heap))])

[9, 7, 8, 2, 3, 4, 6] True
[10, 9, 8, 7]
10 [9, 7, 8]
[9, 8, 7, 6, 4, 3, 2]

[2, 7, 4, 9, 3, 8, 6]에서는 인덱스 2, 1, 0의 순서로 고칩니다. 인덱스 2의 4는 자식 8과 6 가운데 8과 맞바꾸고, 인덱스 1의 7은 자식 9와 맞바꿉니다. 마지막으로 루트의 2가 9와 맞바꾸어 인덱스 1로 내려간 뒤, 그 자리의 자식 7과 3 가운데 7과 다시 맞바꾸어 인덱스 3까지 내려갑니다. 결과는 그림의 힙과 같습니다. 마지막 줄은 힙에서 최댓값을 계속 꺼낸 결과로, 큰 값부터 차례로 나옵니다. 이 생각을 정렬로 발전시킨 것이 다음 글의 힙 정렬입니다.

왜 맞고 왜 끝나는가

위로 올리기에서 힙 조건이 깨질 수 있는 곳은 새 값과 그 부모 사이뿐입니다. 새 값이 부모보다 커서 맞바꾸면, 내려온 부모는 원래 그 자리의 부모였으므로 새 값의 형제였던 노드보다 작지 않아 그 아래의 조건이 지켜지고, 문제가 될 수 있는 곳은 다시 한 층 위로 옮겨 갑니다. 루트에 도착하거나 부모가 더 크면 깨진 곳이 없으므로 힙입니다. 아래로 내리기도 같은 방식으로, 깨질 수 있는 곳이 내려간 값과 그 자식 사이로 한정된 채 한 층씩 내려갑니다. 두 작업 모두 한 번에 한 층씩 움직이고 트리의 높이는 유한하므로 반드시 끝납니다.

한꺼번에 힙 만들기가 맞는 이유는 고치는 순서에 있습니다. 인덱스가 큰 노드부터 고치므로, 어떤 노드를 고칠 때 그 자식들은 이미 고쳐져 각자 아래가 힙입니다. 이 상태에서 아래로 내리기를 하면 그 노드 아래 전체가 힙이 되고, 루트까지 고치면 전체가 힙입니다.

Python의 heapq

Python 표준 라이브러리의 heapq 모듈은 리스트를 최소 힙으로 다루는 함수들을 제공합니다. heappush는 값을 넣고, heappop은 가장 작은 값을 꺼내며, heapify는 리스트를 그 자리에서 최소 힙으로 바꿉니다. 이 함수들은 우리 코드와 같은 방식으로 리스트의 인덱스를 써서 트리를 표현합니다.

우선순위와 함께 다른 정보를 넣을 때는 튜플을 씁니다. 튜플은 첫 번째 값부터 차례로 비교하므로 (우선순위, 정보)처럼 넣으면 우선순위로 정렬됩니다. 응급실 예를 위급도가 작을수록 급하다고 정하고 만들어 보겠습니다.

import heapq

queue = []
arrivals = [(3, "감기"), (1, "골절"), (2, "화상"), (1, "호흡 곤란")]
for order, (urgency, name) in enumerate(arrivals):
    heapq.heappush(queue, (urgency, order, name))
while queue:
    urgency, order, name = heapq.heappop(queue)
    print(urgency, name)

1 골절
1 호흡 곤란
2 화상
3 감기

튜플의 두 번째 값으로 도착 순서 order를 넣은 데는 이유가 있습니다. 위급도가 같은 골절과 호흡 곤란은 먼저 온 골절이 먼저 나오도록 도착 순서로 비교됩니다. 또 순서 값이 서로 다르므로 세 번째 값인 이름까지 비교하는 일이 생기지 않습니다. 정보 부분이 크기를 비교할 수 없는 값이어도 문제없이 동작하는 것입니다. 공식 문서의 heapq에도 이 방법이 소개되어 있습니다. 최대 힙이 필요하면 우선순위에 -1을 곱해 넣는 방법을 흔히 쓰고, Python 3.14부터는 heappush_max, heappop_max 같은 최대 힙 함수도 생겼습니다.

더 깊이: 한꺼번에 만들면 O(n)인 이유

값 n개를 하나씩 넣어 힙을 만들면 넣을 때마다 O(log n)이라 전체가 O(n log n)입니다. 아래에서부터 고치는 방법은 이보다 빠른 O(n)입니다. 노드가 아래로 내려갈 수 있는 층수는 그 노드 아래의 높이를 넘지 못하는데, 높이가 큰 노드는 아주 적기 때문입니다.

완전 이진 트리에서 노드의 약 절반은 리프라서 전혀 내려가지 않습니다. 약 4분의 1은 리프 바로 위라서 많아야 1층, 약 8분의 1은 많아야 2층을 내려갑니다. 그래서 전체 교환 횟수는 많아야 n × (1/4 + 2/8 + 3/16 + …)이고, 괄호 안의 합은 1이므로 n을 넘지 않습니다. 실제로 고치는 노드마다 값이 리프까지 내려가는 오름차순 입력에서 세어 보면, 원소 1000개를 힙으로 만드는 데 교환이 992번 일어나 n보다 적습니다.

정리

• 우선순위 큐는 값을 넣고 우선순위가 가장 높은 값을 꺼내는 자료구조이고, 힙은 두 작업을 모두 O(log n)에 하는 대표적인 구현입니다.
• 완전 이진 트리는 층 순서로 리스트에 담을 수 있으며, 인덱스 i의 자식은 2i + 1과 2i + 2, 부모는 (i - 1) // 2에 있습니다. 노드가 n개이면 높이는 ⌊log₂ n⌋입니다.
• 최대 힙은 모든 부모가 자식보다 작지 않은 완전 이진 트리라서 루트가 최댓값이지만, 전체가 정렬되어 있지는 않습니다.
• 넣을 때는 끝에 붙인 뒤 위로 올리고, 꺼낼 때는 마지막 값을 루트로 옮긴 뒤 큰 자식 쪽으로 내립니다. 리스트 전체는 아래에서부터 고쳐 O(n)에 힙으로 만듭니다.
• Python의 heapq는 최소 힙이며, (우선순위, 순서, 정보) 튜플을 넣으면 같은 우선순위에서 먼저 넣은 값이 먼저 나옵니다.

연습 문제

1. 인덱스로 부모와 자식 찾기

길이가 7인 힙에서 인덱스 4의 부모는 어디인가요? 인덱스 3에는 자식이 있나요?

2. 힙과 정렬된 리스트

[9, 7, 8]은 최대 힙인가요? 정렬된 리스트인가요?

3. 넣고 꺼내기 추적하기

최대 힙 [9, 7, 8, 2, 3, 4]에 10을 넣은 직후의 리스트와, 이어서 최댓값을 하나 꺼낸 직후의 리스트를 구하세요.

다음 글 힙 정렬의 활성 구간과 확정 구간에서는 최대 힙에서 최댓값을 꺼내 리스트 끝에 놓는 일을 되풀이해, 추가 리스트 없이 최악의 경우에도 O(n log n)인 정렬을 만듭니다.