---
title: "가장 작은 것만 꺼낼 건데 전부 정렬할 필요는 없다"
description: "우선순위 큐(priority queue)와 그것을 떠받치는 이진 힙(binary heap) 이야기입니다. 트리처럼 보이지만 배열 하나이고, 넣기와 꺼내기가 왜 둘 다 log n 인지, 유니티에서는 무엇을 쓸 수 있는지 봅니다."
author: "유니얼"
pubDate: 2026-09-17
category: "programming/algorithm/graph"
tags: ["자료구조"]
canonical: https://blog.unialgames.com/posts/algo-priority-queue-heap/
---
칸마다 이동 비용이 다른 맵에서 최단 경로를 찾을 때, 매 단계 하는 일은 하나입니다.
**아직 확정 안 된 후보 중에서 지금까지 든 비용이 가장 적은 것을 꺼냅니다.** 그걸 확정하고 이웃을 다시 후보에 넣습니다.

쿨타임도 같은 모양입니다. 스킬 쉰 개가 각자 다른 시각에 풀린다면, 지금 알아야 하는 것은 **가장 먼저 풀리는 하나**뿐입니다.
나머지 마흔아홉 개의 순서는 알 필요가 없습니다.

전체를 정렬하면 이 연산이 공짜가 되지만, **필요 없는 순서까지 만드느라 값을 치릅니다.**
최솟값 하나만 빠르게 꺼내는 것이 목적이면 정렬보다 싼 방법이 있습니다.

넣기와 "가장 작은 것 꺼내기" 두 가지만 제공하는 자료구조를 **우선순위 큐(priority queue)** 라고 부릅니다.
그리고 그것을 만드는 가장 흔한 방법이 **이진 힙(binary heap)** 입니다. 이 글은 그 둘에 대한 이야기입니다.

## 최솟값만 필요할 때 고를 수 있는 것

| 방법 | 넣기 | 가장 작은 것 꺼내기 | 언제 |
| --- | --- | --- | --- |
| 리스트에 그냥 담기 | `O(1)` | `O(n)` 전부 훑어 최솟값 찾기 | 후보가 몇 개 안 될 때 |
| 정렬된 채로 유지 | `O(n)` 자리를 찾아 밀어넣기 | `O(1)` 맨 앞 | 넣는 일이 드물고 꺼내는 일이 잦을 때 |
| **힙** | `O(log n)` | `O(log n)` | 둘 다 자주 일어날 때 |

길찾기는 세 번째입니다. 넣기와 꺼내기가 번갈아 수만 번 일어납니다.
후보가 1,000개일 때 리스트를 매번 훑으면 꺼낼 때마다 1,000번을 보지만, 힙은 열 번입니다.

**후보가 열 개 안쪽이면 리스트가 더 빠릅니다.** 힙은 분기와 인덱스 계산이 붙는 대신 큰 n 에서 이깁니다.

## 트리처럼 보이지만 배열 하나다

힙은 두 가지 약속으로 정의됩니다.

- **부모는 두 자식보다 작거나 같다.** 그래서 맨 위가 언제나 최솟값입니다. 형제끼리는 순서가 없습니다
- **빈 자리 없이 위에서부터, 왼쪽부터 채운다.** 트리 모양이 언제나 꽉 찬 상태라 배열에 그대로 눕힐 수 있습니다

두 번째 약속 덕분에 **노드를 이어 주는 포인터가 필요 없습니다.** 부모와 자식은 인덱스 계산으로 나옵니다.

```csharp
int Parent(int i) => (i - 1) / 2;
int Left(int i)   => 2 * i + 1;
int Right(int i)  => 2 * i + 2;
```

메모리가 한 덩어리라 캐시에도 유리합니다. 트리는 머릿속에만 있고 실제로는 `int[]` 하나입니다.

## 넣을 때는 위로 올라간다

새 값은 **배열 맨 뒤**에 붙입니다. 모양을 지키려면 거기밖에 자리가 없습니다.
그다음 부모와 견주면서 더 작으면 자리를 바꿉니다. 부모가 더 작아지는 순간 멈춥니다.

<x-binheap>
<script type="application/json">
{
  "label": "넣어 보기",
  "ops": [{ "push": 8 }, { "push": 5 }, { "push": 9 }, { "push": 2 }],
  "note": "위가 트리로 본 모양, 아래가 실제 배열입니다"
}
</script>
</x-binheap>

이렇게 새 값이 제자리를 찾아 올라가는 것을 **올리기(sift up)** 라고 부릅니다.
2가 들어갈 때 두 번 올라가서 맨 위에 섭니다. **바꾸는 것은 지나온 한 줄뿐**이고, 옆으로는 아무것도 안 건드립니다.
형제끼리는 순서가 없어도 되니까요.

```csharp
public void Push(int v) {
    _a.Add(v);
    int i = _a.Count - 1;

    while (i > 0) {
        int p = (i - 1) / 2;
        if (_a[i] >= _a[p]) break;
        (_a[i], _a[p]) = (_a[p], _a[i]);
        i = p;
    }
}
```

## 꺼낼 때는 마지막을 위로 올리고 내려보낸다

맨 위를 꺼내면 루트가 빕니다. 그 자리를 **배열 맨 뒤의 값**으로 메웁니다.
빈칸 없이 채워야 한다는 약속을 지키려면 없앨 수 있는 자리가 마지막 칸뿐이기 때문입니다.

그렇게 올린 값은 대체로 너무 큽니다. 이번에는 **더 작은 자식**과 견주며 내려갑니다.

<x-binheap>
<script type="application/json">
{
  "label": "꺼내 보기",
  "initial": [2, 5, 9, 8],
  "ops": [{ "pop": true }],
  "note": "루트가 빈 자리를 마지막 원소로 메우고, 제자리를 찾아 내려갑니다"
}
</script>
</x-binheap>

내려가는 쪽은 **내리기(sift down)** 입니다. 여기서 **둘 중 더 작은 자식과 바꿔야 합니다.**
큰 쪽과 바꾸면 그 자식이 부모가 되면서 약속이 깨집니다.

```csharp
public int Pop() {
    int top = _a[0];
    int last = _a[^1];
    _a.RemoveAt(_a.Count - 1);

    if (_a.Count > 0) {
        _a[0] = last;
        int i = 0;

        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, m = i;
            if (l < _a.Count && _a[l] < _a[m]) m = l;
            if (r < _a.Count && _a[r] < _a[m]) m = r;
            if (m == i) break;
            (_a[i], _a[m]) = (_a[m], _a[i]);
            i = m;
        }
    }

    return top;
}
```

## 왜 둘 다 log n 인가

올라가는 길과 내려가는 길은 **트리의 높이만큼**입니다. 그리고 빈칸 없이 채운 이진 트리의 높이는 `log n` 입니다.
한 층 내려갈 때마다 노드 수가 두 배가 되니, 100만 개를 담아도 층은 스무 개입니다.

| 원소 수 | 층 수 | 넣거나 꺼낼 때 바꾸는 횟수 (최악) |
| --- | --- | --- |
| 1,000 | 10 | 10 |
| 100만 | 20 | 20 |
| 10억 | 30 | 30 |

**정렬은 전체 순서를 만들지만 힙은 한 줄만 고칩니다.** 그래서 필요한 것이 최솟값 하나일 때 힙이 이깁니다.

반대로 **전체를 순서대로 훑어야 한다면 힙은 답이 아닙니다.** 하나씩 꺼내면 결국 `n log n` 이고, 그럴 거면 처음부터 정렬하는 편이 낫습니다.

## 유니티에서는 무엇을 쓰나

`System.Collections.Generic.PriorityQueue` 는 .NET 6에서 들어온 타입입니다.
그런데 유니티 6의 API 호환성 레벨은 **.NET Standard 2.1 과 .NET Framework 4.8** 두 가지입니다.
둘 중 어느 쪽에도 이 타입이 없습니다. 유니티 프로젝트에서 그냥 쓰려고 하면 컴파일이 안 됩니다.

| 선택지 | 쓸 만한가 |
| --- | --- |
| `PriorityQueue` | **없습니다.** .NET 6 이상 API입니다 |
| `SortedSet` · `SortedList` | 됩니다. 다만 **중복 키를 못 담고**, 트리 노드마다 할당이 생깁니다 |
| 직접 만든 힙 | 위의 코드 정도면 충분합니다. 배열 하나라 할당도 한 번뿐입니다 |
| 패키지로 가져오기 | .NET 구현을 그대로 옮긴 UPM 패키지들이 있습니다 |

길찾기에서는 **같은 비용을 가진 후보가 흔합니다.** 격자에서 대각선 없이 움직이면 비용이 같은 칸이 수두룩합니다.
`SortedSet` 은 그런 값을 하나로 합쳐 버리므로, 쓰려면 비교자에 타이브레이커를 넣어 억지로 다르게 만들어야 합니다.
그럴 바에는 힙을 직접 두는 편이 단순합니다.

유니티가 CoreCLR 로 옮겨 가는 작업이 진행 중이라 이 표는 언젠가 바뀝니다.
다만 **지금 쓰는 버전에서 되는지는 직접 확인하고 시작하세요.** 프로젝트의 API 호환성 레벨 설정에 따라서도 달라집니다.

## 우선순위가 같으면 순서가 보장되지 않는다

힙은 형제끼리 순서를 정하지 않습니다. 그래서 **같은 우선순위끼리는 넣은 순서대로 나온다는 보장이 없습니다.**

대부분은 상관없지만 보이는 결과가 달라지는 자리가 있습니다.
같은 프레임에 끝나는 연출 두 개의 순서가 실행할 때마다 바뀌면 리플레이가 어긋납니다.

넣은 순번을 같이 담아서 두 번째 기준으로 쓰면 됩니다.

```csharp
readonly record struct Item(float Cost, int Seq);

// Cost 가 같으면 먼저 넣은 것이 먼저
int Compare(Item a, Item b) =>
    a.Cost != b.Cost ? a.Cost.CompareTo(b.Cost) : a.Seq.CompareTo(b.Seq);
```

## 값이 바뀌면 어떻게 하나

길찾기를 돌리다 보면 **이미 후보에 넣어 둔 것의 비용이 줄어드는 일**이 생깁니다. 더 싼 경로를 나중에 찾는 경우입니다.
힙에는 "이미 들어 있는 원소의 값을 낮추는" 연산이 기본으로 없습니다. 그 원소가 배열 어디에 있는지 모르기 때문입니다.

방법은 둘입니다.

- **인덱스를 따로 들고 있기.** 이 연산에 붙은 이름이 감소 키(decrease-key)입니다. 값마다 현재 위치를 `Dictionary` 로 관리하면 값을 고치고 그 자리에서 다시 올릴 수 있습니다. 대신 자리를 바꿀 때마다 그 표도 같이 고쳐야 합니다
- **그냥 다시 넣기.** 낮아진 비용으로 하나 더 넣고, 꺼낼 때 이미 확정된 것이면 버립니다. 지연 삭제(lazy deletion)라고 부릅니다

```csharp
var (cost, node) = heap.Pop();
if (visited[node]) continue;   // 낡은 항목이라 버린다
visited[node] = true;
```

**두 번째가 훨씬 단순하고 실제로도 많이 씁니다.** 힙에 쓰레기가 좀 쌓이는 대신 코드가 짧습니다.
간선 수만큼만 더 들어가므로 비용도 크게 안 늘어납니다.

## 정리

힙은 **최솟값 하나만 빠르게 꺼내려고** 만든 자료구조입니다. 전체 순서를 만들지 않는 것이 이득의 출처입니다.

- 부모가 자식보다 작고, 빈칸 없이 채운다는 두 약속이 전부입니다. 그래서 포인터 없이 배열 하나로 됩니다
- 넣으면 위로 올라가고 꺼내면 마지막 원소를 올려 내려보냅니다. 둘 다 **트리 높이만큼**, 즉 `log n` 입니다
- **유니티 6에는 `PriorityQueue` 가 없습니다.** 직접 만들거나 패키지를 가져와야 합니다
- 같은 우선순위의 순서가 중요하면 넣은 순번을 두 번째 기준으로 담습니다
- 값이 낮아지는 경우는 다시 넣고 꺼낼 때 버리는 쪽이 단순합니다