CS 로드맵 (외전) — 힙과 우선순위 큐: 부분 순서의 경제학

게시 2026/04/23

중급

By Sehyup

44 분읽는 시간

CS 로드맵 (외전) — 힙과 우선순위 큐: 부분 순서의 경제학

CS 로드맵 (6) — 메모리 관리: 스택과 힙, GC, ...

TL;DR — 핵심 요약

우선순위 큐는 '최솟값/최댓값만 빠르게' 필요로 하는 문제 — 완전 정렬(O(n log n))은 과잉 사양이다. 힙은 '부분 순서'만 유지하여 O(log n) push/pop을 달성한다
이진 힙은 완전 이진 트리를 배열로 표현한 마법 — 포인터 없이 parent = (i-1)/2, left = 2i+1이라는 인덱스 산술만으로 트리를 오간다
Floyd(1964)의 bottom-up build-heap은 O(n)에 완성된다. 직관과 달리 O(n log n)이 아니다 — 깊은 레벨 노드가 많고 얕은 sift-down만 하기 때문
A* open set의 decrease-key는 실무에서 lazy deletion(stale entry를 꺼낼 때 무시)으로 해결한다. Fibonacci heap의 O(1) decrease-key는 상수 오버헤드 때문에 격자 A*에서는 오히려 손해다

서론

이 문서는 CS 로드맵 시리즈의 외전(bonus)입니다.

5편 그래프에서 Dijkstra와 A를 다루면서 한 문장을 남겼다: *“우선순위 큐(이진 힙)를 사용하면 $O((V+E) \log V)$”. 그런데 그 “이진 힙”이 무엇인지, 왜 이진이고, 어떻게 $O(\log n)$을 달성하는지는 뒤로 미뤘다. 이 외전은 그 빚을 갚는다.

1단계(자료구조와 메모리)가 6편으로 마무리된 뒤, 힙과 우선순위 큐는 “빠진 핵심 한 조각”으로 남아 있었다. 트리의 응용이자 배열의 산술이며, A*의 엔진이자 이벤트 스케줄러의 심장이다. 작은 주제이지만 안 보고 넘기기엔 게임 개발에서 너무 자주 등장한다.

이 글에서 다룰 것:

왜 완전 정렬이 아니라 “부분 순서”로 충분한가
이진 힙이 배열 위에서 동작하는 원리
sift-up / sift-down의 수학적 근거와 C# 구현
Floyd(1964)의 $O(n)$ build-heap
d-ary heap, Pairing heap, Fibonacci heap — 언제 어떤 걸 쓰는가
A* open set의 decrease-key 문제와 실무 해법
.NET PriorityQueue<TElement, TPriority> 분석

Part 1: 우선순위 큐 문제

“최솟값만 빠르게” — 완전 정렬은 과잉이다

다음 문제를 생각해보자.

정수 1,000,000개가 있다. 그중 가장 작은 값 1,000개만 순서대로 꺼내고 싶다.

직관적으로 떠오르는 해법은 전체를 정렬한 뒤 앞에서 1,000개를 취하는 것이다. $O(n \log n)$에 전체를 정렬했으니 출력은 $O(k)$. 그런데 잘 생각해보면 낭비다. 뒤쪽 99만 9천 개의 순서는 우리가 쓰지도 않는다. 필요한 것은 “최솟값 추출”과 “삽입”이라는 두 연산뿐이다.

이것이 우선순위 큐(Priority Queue) 문제다. 큐(FIFO)처럼 “넣고 빼는” 인터페이스지만, 나가는 순서는 “먼저 들어온 것”이 아니라 “우선순위가 가장 높은 것”이다.

일반 큐 (FIFO):                우선순위 큐:

  [4, 7, 1, 9, 3]                [4, 7, 1, 9, 3]
   ↓ dequeue                      ↓ extract-min
   4 (들어온 순서)                1 (가장 작은 값)

게임에서 이 문제가 나타나는 순간들:

A* / Dijkstra: “f 값이 가장 작은 노드를 꺼내라”
이벤트 스케줄러: “실행 시각이 가장 이른 이벤트를 꺼내라”
AI 행동 선택: “지금 가장 유용한 행동의 점수를 꺼내라”
DSP / 오디오 믹싱: “가장 중요한 사운드 채널 N개만 재생하라”

순진한 구현들의 트레이드오프

우선순위 큐를 “왜 배열이나 BST로 하면 안 되는가”를 먼저 짚어야 힙의 가치가 보인다.

구조	insert	extract-min	비고
Unsorted Array	$O(1)$	$O(n)$	넣을 땐 맨 뒤에, 뺄 땐 전체 스캔
Sorted Array	$O(n)$	$O(1)$	이진 탐색으로 위치 찾아도 이동 비용 $O(n)$
Sorted LinkedList	$O(n)$	$O(1)$	탐색이 선형, 이동은 없지만
BST (균형)	$O(\log n)$	$O(\log n)$	포인터 4~5개/노드, 캐시 미스
Binary Heap	$O(\log n)$	$O(\log n)$	배열로 구현, 포인터 0개

표를 보면 “힙이 BST보다 복잡도가 같은데 왜 더 좋은가?” 하는 질문이 자연스럽게 나온다. 답은 상수와 캐시에 있다 — 1편에서 다뤘던 그 이야기가 여기서도 반복된다.

힙의 핵심 아이디어: 부분 순서로 충분하다

우선순위 큐 문제의 핵심 통찰은 이것이다.

우리는 매번 최솟값 하나만 꺼낸다. 나머지 요소들의 상대적 순서는 관심 없다.

전체 정렬은 “모든 쌍에 대해 $a < b$ 또는 $a > b$”를 결정한다. 하지만 최솟값 추출은 “루트가 전체의 최소다”라는 훨씬 약한 조건만 있으면 된다. 이 “약함”이 $O(\log n)$의 여지를 만든다.

힙의 약속 (min-heap):

루트는 전체의 최솟값이다
부모는 두 자식보다 작거나 같다 (형제끼리는 순서 불문)

이것을 힙 속성(heap property)이라고 부른다. BST의 “왼쪽 < 부모 < 오른쪽”과 달리, 힙은 부모-자식 관계만 강제하고 형제나 서브트리 간 순서는 아무렇게나 둔다. 이 “느슨함”이 빠른 삽입/삭제의 비결이다.

Part 2: 이진 힙의 구조

완전 이진 트리

4편 트리에서 완전 이진 트리(complete binary tree)를 정의했다: “마지막 레벨을 제외하고 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 트리”. 이진 힙은 반드시 완전 이진 트리여야 한다.

         1
       /   \
      3     2
     / \   / \
    7   5 4   8
   / \
  9  10

높이 = ⌊log₂(n)⌋ = ⌊log₂(8)⌋ = 3
마지막 레벨은 왼쪽부터 채워졌다

왜 완전이어야 하는가? 두 가지 이유가 있다.

높이가 항상 $\lfloor \log_2 n \rfloor$로 유지됨 — sift-up/down이 $O(\log n)$임을 보장
배열로 표현 가능 — 빈 슬롯이 없으니 배열에 꽉 채울 수 있다

두 번째가 이 자료구조의 마법이다.

배열로 표현된 트리 — 포인터 없는 트리

완전 이진 트리의 노드를 레벨 순서(위에서 아래, 왼쪽에서 오른쪽)로 배열에 저장하면, 부모-자식 관계가 인덱스 산술로 표현된다.

0-based 인덱스 기준:

\[\text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor, \quad \text{left}(i) = 2i+1, \quad \text{right}(i) = 2i+2\]

1-based로 쓰면 더 예쁘다 (Williams의 원 논문이 이 형태를 썼다):

\[\text{parent}(i) = \left\lfloor \frac{i}{2} \right\rfloor, \quad \text{left}(i) = 2i, \quad \text{right}(i) = 2i+1\]

왜 이것이 강력한가?

메모리 연속 — 트리 전체가 하나의 배열. 프리페처가 다음 노드를 미리 가져온다
포인터 0개 — 노드당 value 하나만 저장. 4~5 워드를 쓰는 BST보다 메모리 밀도가 월등
캐시 라인 효율 — 64바이트 캐시 라인 하나에 int 기준 16개 요소. 상위 레벨 몇 개가 L1에 상주

1편에서 “배열은 연속된 메모리에 데이터를 저장하여 캐시 지역성의 이점을 최대로 누린다”고 했다. 힙은 이 원리를 트리에 이식한 자료구조다.

잠깐, 이건 짚고 넘어가자
Q. 1-based 인덱스가 수식이 예쁜데, 왜 실무에선 0-based를 쓰는가?
언어의 배열이 0-based이기 때문이다. array[0]을 비워두고 1번부터 쓰면 메모리 1개 낭비 + 혼란 증가. 대부분의 구현체(C++ std::priority_queue, .NET PriorityQueue)는 0-based를 쓴다. 수식이 조금 덜 예쁠 뿐 동작은 동일하다.
Q. 완전 이진 트리가 아니어도 되지 않는가? 이진 탐색 트리처럼 자유롭게 만들면?
완전성이 깨지면 배열 표현이 불가능해진다 — “빈 자리”를 표현해야 하므로 배열에 sentinel이나 포인터가 필요하고, 이는 BST로 후퇴하는 것이다. 또한 한쪽으로 기울면 높이가 $O(n)$이 되어 연산이 느려진다. “배열에 빈틈 없이”가 힙의 정체성이다.

Part 3: 핵심 연산 — sift-up과 sift-down

힙에서 힙 속성을 유지하는 두 가지 기본 연산이다. 삽입과 삭제가 모두 이 둘로 귀결된다.

sift-up (percolate up) — 삽입

새 요소를 넣을 때의 전략:

배열의 맨 뒤에 새 요소를 추가 (완전성 유지)
부모와 비교, 더 작으면 교환
힙 속성이 회복될 때까지 반복 (또는 루트 도달)

삽입 1:                 단계 1: 부모와 비교     단계 2: 회복 완료
                       [1]                    [1]
     [1]                / \                   / \
    /   \              [3] [2]               [3] [2]
   [3]  [2]            / \ / \               / \ / \
   /\   /\            [7][5][4][8]          [7][5][4][8]
  [7][5][4][8]        / \                    / \
                     [9][1] ← 새 요소         [1][9]  ← 1과 5 비교 → 교환

잠깐, 위 예시는 조금 단순화했다. 실제로 1을 인덱스 9에 넣으면:

초기:       [1, 3, 2, 7, 5, 4, 8, 9]
1을 추가:   [1, 3, 2, 7, 5, 4, 8, 9, 1]  ← 인덱스 8

sift-up:
  i=8, parent(8)=3, heap[3]=7 > 1 → 교환
    [1, 3, 2, 1, 5, 4, 8, 9, 7]
  i=3, parent(3)=1, heap[1]=3 > 1 → 교환
    [1, 1, 2, 3, 5, 4, 8, 9, 7]
  i=1, parent(1)=0, heap[0]=1 ≤ 1 → 멈춤

C# 구현:

  
void SiftUp(int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i].CompareTo(heap[parent]) >= 0)
            break;                        // 힙 속성 만족
        (heap[i], heap[parent]) = (heap[parent], heap[i]);
        i = parent;
    }
}

public void Push(T value) {
    heap.Add(value);
    SiftUp(heap.Count - 1);
}

시간 복잡도: 최악의 경우 루트까지 올라가므로 $O(\log n)$. 트리의 높이가 $\lfloor \log_2 n \rfloor$로 고정되어 있기 때문이다.

sift-down (percolate down) — 삭제 / 최솟값 추출

루트를 꺼내는 연산. 조금 까다롭다.

루트(최솟값)를 반환값으로 저장
배열의 마지막 요소를 루트 위치로 이동
배열 길이를 1 감소 (뒤는 버림)
루트부터 두 자식 중 작은 쪽과 비교, 더 크면 교환
힙 속성이 회복될 때까지 반복 (또는 리프 도달)

핵심은 4번 — 부모가 두 자식보다 작아야 하므로, 두 자식 중 “작은 쪽”과 교환해야 한다. 큰 쪽과 교환하면 그 자식이 형제보다 커져서 속성이 깨진다.

C# 구현:

  
void SiftDown(int i) {
    int n = heap.Count;
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;

        if (left < n && heap[left].CompareTo(heap[smallest]) < 0)
            smallest = left;
        if (right < n && heap[right].CompareTo(heap[smallest]) < 0)
            smallest = right;

        if (smallest == i) break;   // 힙 속성 만족

        (heap[i], heap[smallest]) = (heap[smallest], heap[i]);
        i = smallest;
    }
}

public T Pop() {
    if (heap.Count == 0) throw new InvalidOperationException("Heap is empty");

    T min = heap[0];
    int last = heap.Count - 1;
    heap[0] = heap[last];
    heap.RemoveAt(last);
    if (heap.Count > 0) SiftDown(0);
    return min;
}

public T Peek() {
    if (heap.Count == 0) throw new InvalidOperationException("Heap is empty");
    return heap[0];      // 루트만 보기, O(1)
}

시간 복잡도: 마찬가지로 $O(\log n)$. 단, 주의할 점은 sift-down은 비교 횟수가 sift-up보다 대략 2배라는 것이다 — 각 레벨에서 두 자식과 비교한 뒤 작은 쪽을 골라야 하기 때문. 이 세부사항이 나중에 “왜 Floyd build-heap이 $O(n)$인가”에 영향을 준다.

전체 min-heap 클래스 (참고용)

위 두 연산을 합친 제네릭 min-heap이다.

  
public class MinHeap<T> where T : IComparable<T> {
    private readonly List<T> heap = new();

    public int Count => heap.Count;

    public void Push(T value) {
        heap.Add(value);
        SiftUp(heap.Count - 1);
    }

    public T Pop() {
        if (heap.Count == 0) throw new InvalidOperationException();
        T min = heap[0];
        int last = heap.Count - 1;
        heap[0] = heap[last];
        heap.RemoveAt(last);
        if (heap.Count > 0) SiftDown(0);
        return min;
    }

    public T Peek() => heap.Count > 0 ? heap[0]
        : throw new InvalidOperationException();

    private void SiftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[i].CompareTo(heap[p]) >= 0) break;
            (heap[i], heap[p]) = (heap[p], heap[i]);
            i = p;
        }
    }

    private void SiftDown(int i) {
        int n = heap.Count;
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, s = i;
            if (l < n && heap[l].CompareTo(heap[s]) < 0) s = l;
            if (r < n && heap[r].CompareTo(heap[s]) < 0) s = r;
            if (s == i) break;
            (heap[i], heap[s]) = (heap[s], heap[i]);
            i = s;
        }
    }
}

Part 4: build-heap과 heapsort

Floyd(1964)의 $O(n)$ build-heap

배열 $n$개를 받아 힙으로 만드는 문제를 생각해보자. 가장 단순한 방법은 요소를 하나씩 Push하는 것이다.

  
var heap = new MinHeap<int>();
foreach (int x in array) heap.Push(x);   // O(n log n)

이 경우 각 Push가 $O(\log n)$이므로 전체는 $O(n \log n)$. 정렬과 같은 복잡도다.

하지만 Robert Floyd가 1964년에 발견한 놀라운 사실: 이미 채워진 배열을 힙으로 만드는 것은 $O(n)$에 가능하다.

알고리즘은 간단하다 — 배열의 마지막 비(非)리프 노드부터 뒤에서 앞으로 sift-down을 적용한다.

  
public static void BuildHeap<T>(T[] arr) where T : IComparable<T> {
    // 마지막 비리프의 인덱스는 n/2 - 1
    for (int i = arr.Length / 2 - 1; i >= 0; i--)
        SiftDown(arr, i, arr.Length);
}

왜 $O(n)$인가? 핵심은 “깊은 노드가 많지만 sift-down 거리는 짧다”는 비대칭성이다.

높이 $h$에서의 노드 수는 최대 $\lceil n / 2^{h+1} \rceil$개이고, 각 노드에서 sift-down은 최대 $h$만큼 내려간다. 총 비용은:

\[T(n) = \sum_{h=0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h) = O\left(n \sum_{h=0}^{\infty} \frac{h}{2^h}\right)\]

그리고 무한급수 $\sum_{h=0}^{\infty} h / 2^h = 2$가 상수로 수렴하므로:

\[T(n) = O(2n) = O(n)\]

직관적 그림: 트리의 절반이 리프(이동 안 함), 1/4이 높이 1(한 칸 이동), 1/8이 높이 2(두 칸 이동)… 지배적인 건 많은 리프들이고, 이들은 일을 거의 하지 않는다.

잠깐, 이건 짚고 넘어가자
Q. 왜 sift-up이 아니라 sift-down으로 build-heap을 하는가?
sift-up으로 build-heap을 하면 $O(n \log n)$이 된다. sift-up은 “부모로 올라가는” 연산이고, 리프 근처 노드가 가장 많은데 이들이 루트까지 $\log n$ 올라가야 한다. 반대로 sift-down은 “자식으로 내려가는” 연산이고, 루트 근처 노드는 적지만 $\log n$ 내려가고 리프 근처 노드는 많지만 거의 안 움직인다. 노드 수와 이동 거리의 곱이 선형이 되는 구조다.
Q. 그럼 Push를 $n$번 하는 대신 항상 build-heap을 쓰는 게 좋은가?
배열이 미리 준비된 경우라면 그렇다. 하지만 스트리밍 입력(요소가 하나씩 도착)이면 build-heap을 쓸 수 없으니 Push의 $O(n \log n)$을 받아들여야 한다.

Heapsort — 힙으로 정렬하기

build-heap을 이해했으면 정렬은 공짜로 따라온다. Williams(1964)가 이 아이디어를 정리해서 발표했다.

build-heap으로 배열을 max-heap으로 만든다 — $O(n)$
루트(최댓값)를 배열의 맨 뒤와 교환
마지막 위치를 제외하고 sift-down — $O(\log n)$
반복하면 배열이 오름차순으로 정렬된다

  
public static void HeapSort<T>(T[] arr) where T : IComparable<T> {
    int n = arr.Length;

    // 1. max-heap 빌드 — O(n)
    for (int i = n / 2 - 1; i >= 0; i--)
        SiftDownMax(arr, i, n);

    // 2. 루트와 끝을 교환 후 축소 반복 — O(n log n)
    for (int end = n - 1; end > 0; end--) {
        (arr[0], arr[end]) = (arr[end], arr[0]);
        SiftDownMax(arr, 0, end);
    }
}

시간 복잡도: 최선/평균/최악 모두 $O(n \log n)$
공간 복잡도: $O(1)$ — 제자리(in-place) 정렬
안정성: 불안정(unstable) — 교환이 같은 키 순서를 뒤섞는다

왜 Quicksort에 밀렸는가

이론적 최악 복잡도는 heapsort가 더 낫다 (quicksort는 $O(n^2)$ 최악). 그런데 실무에선 quicksort 계열이 지배한다. 이유:

캐시 지역성이 떨어진다 — sift-down이 i → 2i+1 또는 2i+2로 인덱스를 두 배 점프한다. 배열이 크면 캐시 라인을 벗어나는 접근이 잦다.
비교/교환 횟수가 많다 — 각 sift-down 스텝이 자식 2개와 비교한다. Quicksort/Mergesort는 비교당 1회 이동에 가깝다.
분기 예측 친화성이 떨어진다.

현대 표준 라이브러리들의 선택:

언어 / 표준	정렬 알고리즘
C# `Array.Sort`	Introsort (quicksort + heapsort fallback)
C++ `std::sort`	Introsort
Python `sorted`	Timsort (merge + insertion, 안정)
Java `Arrays.sort` (primitives)	Dual-pivot quicksort
Java `Arrays.sort` (objects)	Timsort
Rust `slice::sort`	Timsort 변형 (안정)

Introsort(Musser 1997)는 평소엔 quicksort, 깊이가 $2\log n$을 넘으면 heapsort로 전환한다. Heapsort는 여기서 “quicksort가 망가질 때의 안전망” 역할을 한다 — 게임 스튜디오에서도 흔히 “나쁜 상황에서의 보장”이 필요할 때 쓰인다.

Part 5: 힙의 변종들 — 언제 binary가 아닌가

이진 힙만 알면 실무의 95%는 해결된다. 그래도 남은 5%를 위해 몇 가지 변종을 살펴보자.

d-ary Heap

각 노드가 $d$개의 자식을 가지는 힙. 부모/자식 인덱스 수식은:

\[\text{parent}(i) = \left\lfloor \frac{i-1}{d} \right\rfloor, \quad \text{child}_k(i) = di + k + 1 \ (k = 0, 1, ..., d-1)\]

트리 높이가 $\log_d n$으로 줄어드는 대신, 각 sift-down에서 $d$개 자식을 비교해야 한다.

연산	Binary ($d=2$)	4-ary	8-ary
sift-up	$\log_2 n$	$\log_4 n$	$\log_8 n$
sift-down	$2 \log_2 n$	$4 \log_4 n = 2 \log_2 n$	$8 \log_8 n \approx 2.67 \log_2 n$

흥미로운 점: 이론적 비교 횟수는 $d=2$와 $d=4$가 거의 같다 ($2\log_2 n$). 그런데 LaMarca & Ladner(1996)의 실험은 4-ary heap이 binary heap보다 실제로 빠르다는 것을 보였다 — 이유는 캐시다.

Binary heap에서 한 부모의 두 자식은 2i+1, 2i+2 — 인접
하지만 조부모에서 손자로 내려가려면 두 번의 점프가 필요
4-ary heap은 한 부모의 네 자식이 4i+1, 4i+2, 4i+3, 4i+4 — 캐시 라인에 모두 들어간다

실무에서 4-ary 또는 8-ary가 binary보다 좋은 경우:

키 크기가 작을 때 (한 캐시 라인에 자식이 모두 들어감)
sift-down이 sift-up보다 훨씬 많을 때 (extract-min 중심 워크로드)
예: 대규모 Dijkstra/A*

Pairing Heap와 Fibonacci Heap

$O(1)$ amortized decrease-key를 제공하는 힙들. Dijkstra의 이론적 복잡도를 $O(E + V \log V)$로 줄인다 (binary heap은 $O((V+E) \log V)$).

힙	insert	extract-min	decrease-key	구조
Binary Heap	$O(\log n)$	$O(\log n)$	$O(\log n)$	배열
4-ary Heap	$O(\log n)$	$O(\log n)$	$O(\log n)$	배열
Pairing Heap	$O(1)$	$O(\log n)$*	$O(\log n)$*	포인터 트리
Fibonacci Heap	$O(1)$	$O(\log n)$*	$O(1)$*	포인터 트리

*amortized (분할 상환)

Fibonacci heap(Fredman & Tarjan 1987)은 이론적 우월성에도 불구하고 실무에서 잘 안 쓰인다:

상수가 크다 — $O(1)$이라도 상수가 커서 $O(\log n)$ binary heap을 실제로 이길 때는 거의 모두 “매우 큰 그래프에서 decrease-key가 많을 때”만
구현이 복잡 — 부모 포인터, 자식 리스트, mark 비트, 랭크, cascading cut 등 관리 포인트가 많다
캐시 재앙 — 포인터 기반 구조라 힙 영역을 돌아다닌다. 1편에서 봤던 linked list의 문제와 같다
decrease-key 자체가 드물다 — A*에서는 lazy deletion으로 회피 가능

Pairing heap(Fredman, Sedgewick, Sleator, Tarjan 1986)은 Fibonacci의 단순화 버전. 이론적 보장은 조금 약하지만 상수가 작아 실측 성능은 종종 Fibonacci보다 낫다. Boost, LEDA 같은 고성능 라이브러리에서 선택지로 제공된다.

잠깐, 이건 짚고 넘어가자
Q. Dijkstra에서 Fibonacci heap을 쓰면 항상 빠른가?
아니다. Chen et al.(2007)과 여러 실측 연구는 실제 데이터셋에서 binary heap 또는 4-ary heap이 Fibonacci heap보다 빠르다는 것을 반복해서 보였다. 이론적 $O(V^2)$ dense graph처럼 $E \gg V$인 극단에서만 Fibonacci가 의미 있는 이점을 보인다.
Q. 그럼 언제 Fibonacci heap을 쓰는가?
실무에선 거의 없다. 이론적 분석을 위한 “존재 증명”의 역할이 크다. 연구 논문, 알고리즘 교재, 그리고 특정 amortized 분석이 필요한 경우에만.

Part 6: 게임 개발에서의 힙

A* open set — decrease-key 문제

5편 Graph의 A* 코드를 다시 보자:

  
List<Vector2Int> AStar(Vector2Int start, Vector2Int goal) {
    var openSet = new PriorityQueue<Vector2Int, float>();
    var gScore = new Dictionary<Vector2Int, float>();
    // ...
    while (openSet.Count > 0) {
        var current = openSet.Dequeue();
        // ...
        foreach (var next in GetNeighbors(current)) {
            float tentativeG = gScore[current] + Cost(current, next);
            if (tentativeG < gScore.GetValueOrDefault(next, float.MaxValue)) {
                gScore[next] = tentativeG;
                openSet.Enqueue(next, tentativeG + Heuristic(next, goal));
            }
        }
    }
}

문제: 같은 노드 next가 이미 open set에 있는데 더 작은 f값으로 다시 들어가면?

교과서적 답은 decrease-key — open set에서 해당 노드를 찾아 우선순위를 낮춘다. 그런데 binary heap은 이 연산이 $O(n)$이다 (해당 원소를 찾아야 하므로). 노드 위치를 별도 Dictionary로 추적하면 $O(\log n)$.

실무적 답은 더 간단하다: lazy deletion.

  
// lazy deletion 패턴
while (openSet.Count > 0) {
    var (current, f) = openSet.Dequeue();

    if (f > gScore[current]) continue;  // stale entry — 이미 더 좋은 값 존재

    if (current == goal) return ReconstructPath(...);

    foreach (var next in GetNeighbors(current)) {
        float tentativeG = gScore[current] + Cost(current, next);
        if (tentativeG < gScore.GetValueOrDefault(next, float.MaxValue)) {
            gScore[next] = tentativeG;
            openSet.Enqueue(next, tentativeG + Heuristic(next, goal));
            // 이전의 stale entry는 그대로 둔다 — 꺼낼 때 체크
        }
    }
}

같은 노드를 여러 번 push해도 문제없다
꺼낼 때 f > gScore[current]로 “이미 유효하지 않음”을 판별
구현 단순, binary heap만으로 충분
메모리는 조금 더 쓰지만 대부분 무시 가능

Unity의 A* Pathfinding Project, Recast/Detour 등 실무 라이브러리 대부분이 이 패턴을 쓴다.

이벤트 / 타이머 스케줄러

게임 서버나 에디터 툴에서 “시각 $t$에 이 작업을 실행하라”를 대량 처리해야 할 때 힙이 적합하다.

  
// 간단한 타이머 큐 — (실행시각, 작업) 페어를 시각 오름차순으로 관리
public class TimerQueue {
    private readonly MinHeap<(float time, Action action)> heap = new();

    public void Schedule(float time, Action action) {
        heap.Push((time, action));       // O(log n)
    }

    public void Tick(float now) {
        while (heap.Count > 0 && heap.Peek().time <= now) {
            var (_, action) = heap.Pop();
            action();                    // O(log n) per dispatch
        }
    }
}

이 패턴은 게임 엔진의 애니메이션 이벤트, 쿨다운, 버프/디버프 만료 처리에서 자주 보인다. 단순한 리스트+매 프레임 스캔 방식은 이벤트 수가 늘수록 선형 비용이 되지만, 힙은 실제로 “지금 만료되는 것”만 꺼낸다.

주의: heap.Peek()도 $O(1)$이므로 “다음 이벤트 시각”을 싸게 알 수 있다. 슬립 타이머를 설정할 때 유용하다.

AI 행동 점수

유틸리티 AI에서 가장 점수가 높은 행동 N개만 고려하고 싶을 때, 크기 $k$로 고정된 min-heap을 사용한다.

  
// 상위 k개 행동 유지
public class TopKActions {
    private readonly MinHeap<(float score, Action action)> heap = new();
    private readonly int k;

    public TopKActions(int k) { this.k = k; }

    public void Consider(float score, Action action) {
        if (heap.Count < k) {
            heap.Push((score, action));
        } else if (score > heap.Peek().score) {
            heap.Pop();                    // 가장 낮은 점수 제거
            heap.Push((score, action));
        }
    }

    public IEnumerable<Action> GetTopK() =>
        heap.ToArray().OrderByDescending(x => x.score).Select(x => x.action);
}

min-heap을 쓰는 게 포인트다. 크기 $k$ top-k 문제에서 min-heap의 루트는 “지금 유지 중인 k개 중 가장 낮은 것”이다. 새 후보가 이보다 크면 교체하면 된다. 이 기법은 일반적인 top-k 문제에서도 널리 쓰인다.

Unity NativeContainer 관점

아쉽게도 Unity는 기본 제공 NativeHeap을 갖고 있지 않다. JobSystem 4편 NativeContainer 심화에서 본 패턴으로 직접 구현해야 한다.

핵심 고려사항:

NativeList<T>를 내부 저장소로 사용 (배열 기반이니 힙과 궁합 좋음)
[NativeContainer] 속성과 AtomicSafetyHandle 연동 — Safety System 통합
Burst 호환: 제네릭 IComparable 대신 struct IComparer<T> 전달 방식 고려
병렬 삽입은 어려움 — sift-up이 루트까지 경쟁하므로 락이 필요. 보통 큐로 수집 후 싱글 스레드에서 pour 패턴

실무에선 BurstAStarGridExample 같은 공식/커뮤니티 예제나, Gilzu의 NativeMinHeap 같은 공개 구현을 참고하는 것이 빠르다.

Part 7: .NET `PriorityQueue<TElement, TPriority>` 분석

.NET 6부터 System.Collections.Generic.PriorityQueue<TElement, TPriority>가 공식 표준으로 추가되었다. 내부는 4-ary min-heap이다 — 위에서 본 이유들 때문에 binary가 아닌 4-ary를 선택했다.

  
var pq = new PriorityQueue<string, int>();
pq.Enqueue("task-a", 3);
pq.Enqueue("task-b", 1);       // 우선순위 숫자가 작을수록 먼저
pq.Enqueue("task-c", 2);

while (pq.Count > 0) {
    string task = pq.Dequeue();
    // task-b, task-c, task-a 순으로 나온다
}

공식 구현의 주요 특징:

TElement와 TPriority 분리 — 큐에 저장되는 값과 정렬 키가 별개 (사용성 향상)
4-ary heap — dotnet/runtime 소스에서 const int Arity = 4로 확인 가능
EnqueueDequeue — push 후 pop을 연달아 할 때의 최적화 (top-k 패턴에 유용)
UnorderedItems — 힙을 “보이는 순서로가 아니라” 저장된 순서로 열거
Dictionary<TElement, ...> 미포함 — decrease-key는 제공하지 않는다. lazy deletion을 써야 한다

주의사항:

스레드 안전 아님 — 멀티스레드 환경에서는 외부 락 필요
중복 키 허용 — 같은 priority로 여러 Enqueue 가능, 순서는 비결정적 (불안정)
안정 정렬이 필요하면 priority를 (originalPriority, tieBreaker) 튜플로 만들어야 함

간단한 A* open set이라면 PriorityQueue<Vector2Int, float> 한 줄로 끝난다. 직접 구현할 이유는 (1) 커스텀 비교자, (2) 특수 할당 패턴, (3) Burst/Job System 통합 정도만 남는다.

정리

핵심 요약

우선순위 큐는 “최솟값/최댓값만”이라는 부분 문제다 — 완전 정렬은 과잉 사양, 부분 순서로 $O(\log n)$을 얻는다
이진 힙은 완전 이진 트리를 배열에 매핑한 구조 — 포인터 0개, 인덱스 산술만으로 부모/자식을 오간다
sift-up과 sift-down이 전부다 — push, pop, 모든 변형 연산이 이 둘의 조합이다
Floyd의 $O(n)$ build-heap — 깊은 노드가 많고 얕은 이동만 필요하다는 비대칭성의 귀결
실무에선 4-ary heap이 binary heap을 이긴다 — 캐시 라인에 자식이 몰리는 레이아웃 이점
Fibonacci heap은 이론용 — 실측에서 binary/4-ary에 밀리고 구현 복잡도만 높다
A* decrease-key는 lazy deletion으로 회피 — 꺼낼 때 stale 체크, push는 그냥 중복 허용
.NET PriorityQueue<TElement, TPriority>는 4-ary heap — 직접 구현할 이유가 많지 않다

어느 층위의 통찰인가

1편 배열과 연결 리스트에서 봤던 “캐시가 복잡도보다 중요할 수 있다“는 명제가 여기서도 반복된다. Fibonacci heap의 이론적 $O(1)$ decrease-key가 실무에서 binary heap에 지는 것은, 우리가 이론과 현실 사이의 상수를 과소평가했기 때문이다.

그리고 힙은 “BST보다 약한 구조가 특정 문제에선 더 강하다”는 예시이기도 하다. “부분 순서”만 유지하는 대가로 배열 매핑이라는 공짜 선물을 받는다. 자료구조 설계에서 “얼마나 적게 약속할 수 있는가”가 오히려 자유도를 높인다는 관점 — BST보다 힙, 전체 정렬보다 top-k. CS의 많은 아이디어가 이 방향으로 흐른다.

이 외전을 끝으로 1단계(자료구조와 메모리) 주변의 빚을 정리했다. 다음부터는 예정대로 2단계: OS와 동시성으로 들어간다. 프로세스, 스레드, 락, 그리고 멀티코어에서의 재난들을 살펴본다.

참고 자료

원전 및 주요 논문

Williams, J.W.J., “Algorithm 232: Heapsort”, Communications of the ACM 7(6), pp. 347–348 (1964) — binary heap의 원전
Floyd, R.W., “Algorithm 245: Treesort 3”, Communications of the ACM 7(12), p. 701 (1964) — $O(n)$ build-heap
Johnson, D.B., “Priority queues with update and finding minimum spanning trees”, Information Processing Letters 4(3), pp. 53–57 (1975) — d-ary heap
Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E., “The pairing heap: A new form of self-adjusting heap”, Algorithmica 1(1), pp. 111–129 (1986)
Fredman, M.L. & Tarjan, R.E., “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM 34(3), pp. 596–615 (1987)
LaMarca, A. & Ladner, R.E., “The influence of caches on the performance of heaps”, ACM Journal of Experimental Algorithmics 1, Article 4 (1996) — 4-ary heap이 binary보다 빠른 실증
Dutton, R.D., “Weak-heap sort”, BIT Numerical Mathematics 33(3), pp. 372–381 (1993)
Brodal, G.S., “Worst-case efficient priority queues”, Proceedings of SODA (1996)
Chen, M., Chowdhury, R.A., Ramachandran, V., Roche, D.L., Tong, L., “Priority Queues and Dijkstra’s Algorithm”, UT Austin Technical Report TR-07-54 (2007) — Fibonacci vs binary 실측 비교

교재

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms (CLRS), 4th Edition, MIT Press — Chapter 6 (Heapsort), Chapter 19 (Fibonacci Heaps)
Sedgewick, R. & Wayne, K., Algorithms, 4th Edition, Addison-Wesley — Chapter 2.4 Priority Queues
Knuth, D., The Art of Computer Programming Vol. 3: Sorting and Searching, 2nd Edition, Addison-Wesley — Section 5.2.3 Sorting by Selection (heapsort)
Weiss, M.A., Data Structures and Algorithm Analysis in C++, 4th Edition, Pearson — Chapter 6 Priority Queues

구현 참고

.NET PriorityQueue<TElement, TPriority> — dotnet/runtime 소스: 4-ary min-heap 공식 구현
C++ std::priority_queue — libstdc++, libc++: binary heap 기반
Java java.util.PriorityQueue — OpenJDK: binary heap 기반
Python heapq — CPython 소스: binary min-heap, 튜플로 priority 지정
Boost Heap — boost.org/libs/heap: binary, d-ary, pairing, Fibonacci, skew heap을 모두 제공

게임 개발 맥락

Millington, I. & Funge, J., Artificial Intelligence for Games, 3rd Edition, CRC Press — A*, open set 관리
Recast & Detour — github.com/recastnavigation: 실무 NavMesh 라이브러리의 힙 활용
A* Pathfinding Project (Unity) — arongranberg.com/astar: lazy deletion 기반 open set

AI, CS