가장 작은 것만 꺼낼 건데 전부 정렬할 필요는 없다

칸마다 이동 비용이 다른 맵에서 최단 경로를 찾을 때, 매 단계 하는 일은 하나입니다. 아직 확정 안 된 후보 중에서 지금까지 든 비용이 가장 적은 것을 꺼냅니다. 그걸 확정하고 이웃을 다시 후보에 넣습니다.

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

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

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

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

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

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

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

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

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

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

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

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

넣을 때는 위로 올라간다

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

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

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;
    }
}

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

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

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

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

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만 개를 담아도 층은 스무 개입니다.

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

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

유니티에서는 무엇을 쓰나

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

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

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

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

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

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

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

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)라고 부릅니다

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

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

정리

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

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