트리와 힙 안내서 · 6/6

실무 활용

트리와 힙은 직접 구현할 일보다 이미 만들어진 형태로 만날 일이 훨씬 많습니다. 이 장에서는 실제 시스템에서 이 구조들이 어디에 쓰이는지, 표준 라이브러리를 쓸 때 자주 빠지는 함정은 무엇인지 정리합니다.

어디에 쓰이나

계층 데이터: 파일 시스템의 디렉터리, 브라우저의 DOM, 컴파일러의 구문 트리(AST), JSON · XML 문서는 모두 트리입니다. 폴더 크기 계산은 후위 순회, 화면 그리기는 전위 순회와 같은 구조입니다.
데이터베이스 인덱스: PostgreSQL, MySQL(InnoDB), SQLite의 기본 인덱스는 B-트리 계열입니다. 노드 하나에 키를 수백 개 담아 높이를 3~4 정도로 낮추고, 디스크 읽기 횟수를 줄입니다. 원리는 BST를 여러 갈래로 넓힌 것입니다.
정렬된 맵과 집합: C++의 std::map · std::set(대부분 레드-블랙 트리), Java의 TreeMap · TreeSet(레드-블랙 트리)은 키를 정렬된 상태로 유지해 floorKey, lower_bound 같은 "가장 가까운 값" 질의를 O(log n)에 처리합니다.
운영체제 스케줄러: Linux 커널은 실행 대기 중인 작업을 레드-블랙 트리에 두고 다음에 실행할 작업을 빠르게 고릅니다.
타이머와 이벤트 루프: Node.js가 쓰는 libuv와 Go 런타임은 타이머를 최소 힙 계열 구조로 관리해 가장 먼저 만료될 타이머를 즉시 찾습니다.
그래프 알고리즘: 다익스트라 최단 경로, 프림 최소 신장 트리, A* 탐색은 "지금까지 가장 가까운 후보"를 우선순위 큐에서 꺼냅니다.
스트림 처리: 상위 K개 집계, 여러 정렬된 파일을 합치는 외부 정렬, 이벤트 시뮬레이션에 힙이 쓰입니다.

Python heapq의 함정

heapq는 리스트를 최소 힙으로 다루는 함수 모음입니다. 최대 힙이 필요하면 값에 -1을 곱해 넣는 방법이 가장 흔합니다(Python 3.14부터는 heappush_max 같은 최대 힙 함수도 제공됩니다). 우선순위가 같은 원소가 있으면 튜플의 다음 원소를 비교하므로, 비교할 수 없는 객체(딕셔너리 등)가 오면 TypeError가 납니다. 증가하는 순번을 중간에 넣으면 해결되고, 같은 우선순위끼리 들어온 순서도 지켜집니다.

import heapq
import itertools

queue, counter = [], itertools.count()


def add(priority, task):
    heapq.heappush(queue, (priority, next(counter), task))


add(2, {"name": "backup"})
add(1, {"name": "deploy"})
add(2, {"name": "report"})       # 우선순위가 같아도 dict 를 비교하지 않음
while queue:
    p, _, task = heapq.heappop(queue)
    print(p, task["name"])       # 1 deploy, 2 backup, 2 report

scores = [5, 1, 9, 3]
max_heap = [-s for s in scores]   # 부호를 뒤집어 최대 힙처럼 쓴다
heapq.heapify(max_heap)
print(-max_heap[0], heapq.nlargest(2, scores))  # 9 [9, 5]

힙은 임의 원소의 우선순위를 바꾸거나 지우는 연산을 직접 지원하지 않습니다. 이때는 새 항목을 다시 넣고 옛 항목은 "무효" 표시만 해 둔 뒤, 꺼낼 때 무효 항목을 건너뛰는 지연 삭제를 씁니다. 다익스트라 구현에서 if d > dist[u]: continue 한 줄이 바로 이 기법입니다.

C++ priority_queue의 함정

std::priority_queue는 기본이 최대 힙입니다. 최소 힙은 세 번째 템플릿 인자로 std::greater를 줍니다. top()과 pop()이 나뉘어 있고, 비어 있을 때 호출하면 정의되지 않은 동작이므로 empty()를 먼저 확인합니다.

#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::priority_queue<int> maxq;  // 최대 힙
    std::priority_queue<int, std::vector<int>, std::greater<int>> minq;  // 최소 힙
    for (int x : {5, 1, 9, 3}) { maxq.push(x); minq.push(x); }
    std::cout << maxq.top() << ' ' << minq.top() << '\n';  // 9 1

    using Item = std::pair<int, std::string>;  // (거리, 이름) 는 pair 비교 규칙을 따름
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;
    pq.push({7, "b"});
    pq.push({3, "a"});
    std::cout << pq.top().second << '\n';  // a
}

Java PriorityQueue의 함정

PriorityQueue는 기본이 최소 힙이고, Comparator로 순서를 바꿉니다. 비교자를 (a, b) -> a - b처럼 빼기로 만들면 큰 수에서 오버플로가 나므로 Integer.compare나 Comparator.comparingInt를 씁니다. 또 for 문이나 toString()으로 보면 내부 배열 순서가 나올 뿐 정렬 순서가 아닙니다. 순서대로 보려면 poll()로 꺼내야 합니다.

import java.util.Comparator;
import java.util.PriorityQueue;

public class Tasks {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
        max.addAll(java.util.List.of(5, 1, 9, 3));
        System.out.println(max.peek()); // 9

        PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        pq.add(new Task("backup", 2));
        pq.add(new Task("deploy", 1));
        while (!pq.isEmpty()) System.out.println(pq.poll().name()); // deploy, backup
    }
}

정리

트리는 파일 시스템, 데이터베이스 인덱스, 정렬된 맵, 스케줄러처럼 시스템의 뼈대 곳곳에 있고, 힙은 타이머와 그래프 알고리즘, 상위 K개 계산의 기본 도구입니다. 표준 라이브러리를 쓸 때는 기본 순서(Python · Java는 최소 힙, C++은 최대 힙), 같은 우선순위의 처리, 우선순위 변경 시 지연 삭제를 기억하면 대부분의 함정을 피할 수 있습니다.

더 읽을거리

이 장에 대해 질문이 있나요?