優先度キュー

優先度キューとは

優先度キュー (Priority Queue) は、各要素に優先度を付与し、優先度の最も高い (または低い) 要素から取り出すデータ構造である。通常のキュー (FIFO) が挿入順に取り出すのに対し、優先度キューは優先度順に取り出す。内部的にはヒープ (Heap) で実装されることが多い。

計算量

二分ヒープで実装した場合の計算量は次のとおりで、要素数 n がいくら増えても挿入と取り出しが対数時間に収まる点に価値がある。取り出しのたびに配列全体を走査する素朴な実装なら取り出しは O(n) で、n が 100 万なら 20 回程度の比較と 100 万回の比較という差になる。

操作	計算量
挿入 (enqueue)	O(log n)
最高優先度の取り出し (dequeue)	O(log n)
最高優先度の参照 (peek)	O(1)

「優先度が高い」がどちらの向きを指すかは実装側の約束事で、下のコード例では優先度の数値が小さい要素を先に取り出す最小ヒープにしている。もう 1 つ注意したいのは、二分ヒープは同じ優先度の要素どうしの順序を保証しないことだ。同順位を挿入順に処理したいなら、優先度と挿入連番の組を比較キーにする必要がある。

TypeScript での実装

標準ライブラリに優先度キューを持たない言語では、配列 1 本で二分ヒープを組むのが定石になる。インデックス i の親が (i - 1) / 2 の切り捨て、子が 2i + 1 と 2i + 2 になる性質を使うと、木構造のポインタを持たずに親子をたどれる。

class MinHeap<T> {
  private heap: { priority: number; value: T }[] = [];

  enqueue(value: T, priority: number): void {
    this.heap.push({ priority, value });
    this.bubbleUp(this.heap.length - 1);
  }

  dequeue(): T | undefined {
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min.value;
  }

  peek(): T | undefined {
    return this.heap.length > 0 ? this.heap[0].value : undefined;
  }

  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent].priority <= this.heap[i].priority) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  private bubbleDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < n && this.heap[left].priority < this.heap[smallest].priority) smallest = left;
      if (right < n && this.heap[right].priority < this.heap[smallest].priority) smallest = right;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

実務での活用

SQS でのメッセージ優先度

SQS には標準キューにも FIFO キューにもメッセージ単位で優先度を指定する仕組みが無く、標準キューの配信は少なくとも 1 回・順序はベストエフォートである (2026 年 8 月時点)。優先度を表現するには、優先度ごとに別のキューを作り、高優先度キューから先に処理する。

// 高優先度キューを先にポーリング
const highPriority = await sqs.receiveMessage({ QueueUrl: HIGH_QUEUE });
if (highPriority.Messages?.length) {
  await processMessages(highPriority.Messages);
} else {
  const lowPriority = await sqs.receiveMessage({ QueueUrl: LOW_QUEUE });
  await processMessages(lowPriority.Messages ?? []);
}

この形には落とし穴が 2 つある。1 つは、待ち時間を指定しない受信 (既定のショートポーリング) がサーバーの一部だけを照会する仕様のため、高優先度キューにメッセージが残っていても空応答が返り得ることだ。空応答を「高優先度は空」と解釈すると、低優先度の処理へ流れて高優先度が待たされる。もう 1 つは、逆に高優先度キューへロングポーリングの待ち時間 (最大 20 秒) を設定すると、その待機中は低優先度キューを 1 件も処理できないことだ。優先度の逆転を避けたいなら、キューごとにコンシューマーを分けて並行に受信し、処理側へ割り当てる同時実行数の比で優先度を表現する方が素直である。

タスクスケジューリング

OS のプロセススケジューラ、ネットワークパケットの QoS、ジョブキューの優先度制御に使われる。ただし純粋な優先度順は、高優先度が流れ続ける間に低優先度が永久に後回しになる飢餓 (starvation) を招く。実務では待ち時間に応じて優先度を上げるエージングや、優先度クラスごとに処理枠を割り当てる方式を併用する。

ダイクストラ法

最短経路アルゴリズム (ダイクストラ法) は、優先度キューを使って「次に探索するノード」を効率的に選択する。二分ヒープを併用すると計算量は O((V + E) log V) になり、未探索ノードを毎回線形に探す実装の O(V^2) より、辺の少ない疎グラフで有利になる。

通常のキューとの使い分け

選択の基準は「取り出す順番を決めるのは到着時刻か、要素が持つ値か」の一点に尽きる。到着順で困らなければ通常のキューで十分で、優先度キューはヒープを維持するコストと実装量を払うだけの理由 (締め切り・重要度・コストの差) があるときに選ぶ。

データ構造	取り出し順	用途
キュー (FIFO)	挿入順	メッセージキュー、タスクキュー
スタック (LIFO)	逆挿入順	関数呼び出し、Undo
優先度キュー	優先度順	スケジューリング、最短経路

さらに掘り下げるなら関連書籍が参考になる。