CSロードマップ (番外編) — ヒープと優先度キュー：部分順序の経済学

投稿 2026/04/24

中級

By Sehyup

49 分読む時間

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千個の順序は使っていない。必要なのは「最小値の取り出し」と「挿入」という2つの操作だけである。

これが優先度キュー（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 (balanced)	$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）：

ルートは全体の最小値である
親は2つの子より小さいか等しい（兄弟同士は順序不問）

これをヒープ特性（heap property）と呼ぶ。BSTの「左 < 親 < 右」とは異なり、ヒープは親子関係のみを強制し、兄弟やサブツリー間の順序は任意に任せる。この「緩さ」が高速な挿入・削除の秘訣だ。

Part 2: 二分ヒープの構造

完全二分木

第4回ツリーで完全二分木（complete binary tree）を定義した：「最後のレベルを除くすべてのレベルが完全に埋まっており、最後のレベルは左から詰められた木」。二分ヒープは必ず完全二分木でなければならない。

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

高さ = ⌊log₂(n)⌋ = ⌊log₂(8)⌋ = 3
最後のレベルは左から詰められている

なぜ完全でなければならないのか？理由は2つある。

高さが常に$\lfloor \log_2 n \rfloor$に保たれる — sift-up/downが$O(\log n)$であることを保証
配列で表現可能 — 空きスロットがないため配列にぎっしり詰められる

2番目がこのデータ構造の魔法だ。

配列で表現された木 — ポインタのない木

完全二分木のノードをレベル順（上から下、左から右）に配列に格納すると、親子関係がインデックス演算で表現される。

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

ヒープでヒープ特性を維持する2つの基本操作だ。挿入と削除がどちらもこの2つに帰着する。

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減らす（末尾は捨てる）
ルートから2つの子のうち小さい方と比較、大きければ交換
ヒープ特性が回復するまで繰り返す（またはリーフに到達）

ポイントは4番 — 親は2つの子より小さくなければならないので、2つの子のうち「小さい方」と交換しなければならない。 大きい方と交換するとその子が兄弟より大きくなって特性が壊れる。

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倍であることだ — 各レベルで2つの子と比較し、小さい方を選ぶ必要があるからだ。この細部が後に「なぜFloyd build-heapが$O(n)$なのか」に影響する。

完全なmin-heapクラス（参考）

上記2つの操作を組み合わせたジェネリック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段移動）、1/8が高さ2（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とインデックスを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で一人の親の2つの子は2i+1, 2i+2 — 隣接
しかし祖父母から孫に降りるには2回のジャンプが必要
4-ary heapは一人の親の4つの子が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回で見た連結リストの問題と同じだ
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より速いことを繰り返し示している。$E \gg V$のdense graphのような極端なケースでのみFibonacciが意味のある優位性を示す。
Q. ではいつFibonacci heapを使うのか？
実務ではほぼない。理論分析のための「存在証明」としての役割が大きい。研究論文、アルゴリズム教科書、そして特定のamortized分析が必要な場合にのみ。

Part 6: ゲーム開発におけるヒープ

A* open set — decrease-key問題

第5回グラフの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がルートまで競合するのでロックが必要。通常はキューで収集後にシングルスレッドで流し込むパターン

実務ではUnity公式の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、すべての変形操作がこの2つの組み合わせだ
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

この記事は著者の CC BY 4.0 ライセンスの下で提供されています。