ヒープと優先度付きキューの内部

優先度付きキューが解く問題

優先度付きキュー（priority queue）は「今ある要素のうち最小（または最大）を取り出す」操作を主役にする抽象データ型です。FIFOのキューが入れた順を守るのに対し、こちらは順序を無視して最優先の1つを高速に返します。タスクスケジューラ、ダイクストラ法やプリム法、ハフマン符号、イベント駆動シミュレーションなど、応用は広範です。

素朴に実装すると壁にぶつかります。ソート済み配列なら最小取り出しは O(1) ですが挿入が O(n)、未ソート配列なら挿入は O(1) でも最小探索が O(n)。どちらかが必ず重い。この挿入と取り出しの両方を O(log n) に揃える定番の解が二分ヒープ（binary heap）です。各操作の速さを表す計算量（Big-O）の記法は前提として進めます。

二分ヒープ ― 完全二分木を配列で表す

二分ヒープは2つの性質を同時に満たす二分木です。

• ヒープ条件: 親は子以下（最小ヒープの場合）。これは根が全体の最小であることだけを保証し、左右の兄弟間に順序はない（探索木との決定的な違い）。
• 完全二分木: 最下段を除き全段が埋まり、最下段は左詰め。形に隙間がない。

この「完全」という形の縛りが効きます。隙間がないので、木を幅優先順に1列に並べた配列でそのまま表現でき、ポインタが一切要りません。0始まりの配列なら添字 i のノードについて、

親      : (i - 1) / 2   （切り捨て）
左の子  : 2*i + 1
右の子  : 2*i + 2

という算術だけで親子を行き来できます。ポインタで木を組むよりメモリが密でキャッシュに乗りやすく、ノード確保も不要です。これがヒープが実務で多用される地味な強みです。

sift-up と sift-down ― 形を保ったまま順序を直す

挿入・取り出しは、まず形（完全二分木）を壊さずに要素を出し入れし、崩れたヒープ条件を1経路だけ辿って修復します。修復の向きが2種類あります。

挿入（sift-up / 上方修正）: 新要素を配列の末尾（＝最下段の右端の次）に置く。形は保たれるが、親より小さいとヒープ条件が崩れる。そこで親と比較し、小さければ親と交換を、条件を満たすか根に着くまで繰り返す。経路は葉から根への一本道なので、交換回数は高々木の高さ＝O(log n)。

末尾（7 の子）に 2 を挿入し、親と比較しながら上げる

      5                5                2
     / \              / \              / \
    8   7     →      8   2     →      8   5
   / \  / \         / \  / \         / \  / \
  9 10 … 2         9 10 … 7         9 10 … 7
   2 < 7 で交換      2 < 5 で交換      根に到達、終了

取り出し（sift-down / 下方修正）: 根（最小）を取り出したい。末尾要素を根へ移して末尾を削れば形は保たれるが、その値は大きすぎてヒープ条件を破る。そこで2人の子のうち小さい方と比較し、自分が大きければその子と交換を、両方の子以下になるか葉に着くまで繰り返す。経路は根から葉への一本道で、やはり O(log n)。

peek（最小の参照） : O(1)   ← 根 = 配列[0] を見るだけ
insert（挿入）      : O(log n) ← sift-up
extract-min（取出） : O(log n) ← 末尾を根へ→sift-down

下方修正で2人の子のうち小さい方を選ぶのが要点です。大きい方と交換すると、交換後にそちらの枝でヒープ条件が崩れ、修復が破綻します。

ビルドヒープがO(n)になる理由

n個の要素から一気にヒープを組むビルドヒープ（build-heap）には、直感に反する結果があります。「n回挿入すれば O(n log n) では？」と思えますが、下から sift-down を積むと O(n) で済みます。

手順は、配列をそのまま完全二分木とみなし、最後の内部ノードから根に向かって順に sift-down をかけるだけです。葉（後半の約半分）は子を持たず修復不要なので飛ばします。

なぜ O(n) か。sift-down のコストはそのノードの高さに比例し、木の高さ全体ではありません。高さ h のノードは約 n / 2^(h+1) 個あります。総コストは各高さの「ノード数 × 高さ」の総和で、

総コスト ≒ n * Σ (h / 2^(h+1))   （h = 0,1,2,…）

ここで Σ (h / 2^h) は 2 に収束する有限和。
よって 総コスト = O(n)。

直感的には、最も数が多い下段のノードはほとんど動かず（高さ0〜1）、高くつく上段のノードはごく少数だからです。逆に sift-up を上から積む方式だと、数の多い下段ノードが最大の高さを登るため O(n log n) に戻ってしまう。修復の向き一つで定数倍ではなくオーダーが変わる、ヒープで最も誤解されやすい点です。

二分ヒープの弱点 ― マージとdecrease-key

二分ヒープは挿入・取り出しに優れますが、2つの操作が重いままです。

• マージ（meld）: 2つのヒープを1つに統合する。配列表現では結局作り直しに近く O(n)。
• decrease-key: 既存要素の優先度を下げる（小さくする）。位置を特定できれば sift-up で O(log n) だが、それでも対数コストがかかる。

ダイクストラ法では、隣接ノードの暫定距離を更新する decrease-key が辺の数だけ呼ばれます。ここを軽くできれば、最短経路探索そのものが速くなる。これが、より高度なヒープが生まれた動機です。

二項ヒープとフィボナッチヒープ ― 償却で軽くする

二項ヒープ（binomial heap）は、サイズが2の冪に対応する二項木の森として要素を保持します。各二項木の根を連結リストでつなぐため、2つのヒープのマージは2進数の足し算と同型になり O(log n) で済みます。挿入・取り出しも O(log n) を保ちつつ、二分ヒープが苦手なマージを対数化したのが利点です。

フィボナッチヒープ（Fibonacci heap, 1984年 Fredman と Tarjan）は、ここから償却計算量を徹底的に削ります。鍵は「修復を怠けて先送りする」設計です。挿入やマージでは木を整理せず根のリストに放り込むだけにし、extract-min のときにまとめて木を統合（consolidate）します。これにより、

ここでの O(1) は最悪ではなく**償却（amortized）**である点が肝心です。個々の操作は時に重くなりますが、操作列全体でならすと1回あたり定数に収まる、という保証です。decrease-key の O(1) 償却は、優先度を下げたノードを親から切り離して根リストへ移すだけにし、切り離しが連鎖した分のツケを後の extract-min に付け替えることで実現します（cascading cut）。名前の由来は、各木のサイズ下限の解析にフィボナッチ数列が現れることです。

ダイクストラ法への寄与

V頂点・E辺のグラフでのダイクストラ法は、優先度付きキューの実装で計算量が変わります。

キューの実装          全体計算量
配列（線形探索）      O(V^2)
二分ヒープ            O((V + E) log V)
フィボナッチヒープ    O(E + V log V)   ← 理論上の最良

ダイクストラは extract-min を V 回、decrease-key を最大 E 回呼びます。二分ヒープでは両方が O(log V) なので合計 O((V + E) log V)。フィボナッチヒープなら decrease-key が償却 O(1) に落ちるため、E 個の更新の対数係数が消え、O(E + V log V) になります。辺が多い密グラフ（E が V^2 に近い）ほど、この差は理論上大きく効きます。

まとめ

ヒープの核心は「根への順序だけを保ち、形を完全二分木に縛る」という割り切りにあります。形の縛りが配列1本での表現を可能にし、sift-up / sift-down が1経路の修復で挿入・取り出しを O(log n) に揃える。ビルドヒープが O(n) になるのは、コストの安い下段ノードが大多数で総和が収束するからで、修復の向きがオーダーを決めます。二項・フィボナッチヒープはマージと decrease-key を償却で軽くし、ダイクストラ法を理論上 O(E + V log V) まで押し下げます。ただし実務では定数倍とキャッシュ効率から二分ヒープが標準であり、これは順序付き集合を支える平衡木とは別系統の、優先度に特化したデータ構造です。