IT 技書の森

優先度キュー

要素に優先度を付与し、優先度の高い要素から取り出すデータ構造

データ構造アルゴリズム

優先度キューとは

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

計算量

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

TypeScript での実装

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

  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 標準キューには優先度の概念がない。優先度を実現するには、優先度ごとに別のキューを作成し、高優先度キューから先に処理する。

// 高優先度キューを先にポーリング
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 ?? []);
}

タスクスケジューリング

OS のプロセススケジューラ、ネットワークパケットの QoS、ジョブキューの優先度制御に使われる。

ダイクストラ法

最短経路アルゴリズム (ダイクストラ法) は、優先度キューを使って「次に探索するノード」を効率的に選択する。

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

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

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

関連用語