JavaScriptで学ぶ優先キュー（Priority Queue）の基本と実装

優先キューとは？

優先キュー（Priority Queue）は、通常のキュー（待ち行列）やスタックに似た抽象データ型の一つですが、大きな違いとして各要素に「優先度」が関連付けられているという特徴を持っています。

通常のキューでは先に入れた要素から順に取り出されます（FIFO：First In, First Out）が、優先キューでは優先度の高い要素が優先度の低い要素よりも先に取り出されるのがルールです。

また、複数の要素が同じ優先度を持つ場合には、それらはキューに追加された順序（FIFO）に従って処理されます。

優先キューの活用例

優先キューは実際の開発でも幅広く利用されています。代表的な例としては以下のようなものが挙げられます。

• タスクスケジューラ：緊急度の高いジョブを先に実行する
• ダイクストラ法などのグラフ探索アルゴリズム：コスト（距離）が最小のノードを効率的に取り出す
• イベント駆動システム：重要度に応じてイベントを処理順に並べる

配列を使ったシンプルな実装

優先キューの実装方法にはいくつかのアプローチがあります。本記事では、最も理解しやすい配列（Array）を使用した実装を紹介します。

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  // 要素を優先度付きで追加
  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;

    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }

  // 最も優先度の高い要素を取り出す
  dequeue() {
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

この実装では、enqueueメソッドで要素を挿入する際に優先度を比較し、適切な位置に挿入しています。数値が小さいほど高い優先度として扱われます。

注意点

配列ベースの実装はシンプルで直感的ですが、要素の挿入時に線形探索が発生するため、パフォーマンス面では非効率です。大量のデータを扱う場合は、二分ヒープ（Binary Heap）を使った実装が一般的で、挿入・削除ともに O(log n) の計算量を実現できます。