JavaScriptで優先度付きキュー（PriorityQueue）に要素を追加する方法

優先度付きキュー（PriorityQueue）への要素追加（エンキュー）とは、各要素が持つ優先度に従って、配列内の適切な位置へ要素を挿入することを指します。本記事では、数値が大きいほど優先度が高いというルールを採用します。基本的な考え方はシンプルで、コンテナ内を先頭から順に走査し、「現在の要素より優先度が低い要素」が見つかった時点でその位置に新しい要素を挿入します。該当する位置が見つからなかった場合は、コンテナの末尾に要素を追加します。

なお、この実装ではデータ（data）と優先度（priority）を持つ要素オブジェクトを作成しています。そのため、enqueue関数は次のように実装できます。

実装例：enqueue関数

enqueue(data, priority) {
   // キューが満杯かどうかをチェック
   if (this.isFull()) {
      console.log("Queue Overflow!");
      return;
   }
   let currElem = new this.Element(data, priority);
   let addedFlag = false;
   // 優先度を比較しながら走査し、適切な位置に挿入
   for(let i = 0; i < this.container.length; i ++) {
       if(currElem.priority < this.container[i].priority) {
          this.container.splice(i, 0, currElem);
         addedFlag = true; break;
       }
   }
   // 挿入位置が見つからなければ末尾に追加
   if (!addedFlag) {
      this.container.push(currElem);
   }
}

コードのポイント

• this.isFull() でキューが満杯かどうかを事前に確認し、オーバーフローを防止しています。
• new this.Element(data, priority) により、データと優先度をまとめたオブジェクトを生成します。
• splice(i, 0, currElem) を使うことで、配列の任意の位置に要素を破壊的に挿入できます。
• 挿入位置が一度も見つからなかった場合（＝最も高い優先度の場合）は、push() で末尾に追加します。

動作確認

以下のコードを実行して、この関数が正しく動作するか確認してみましょう。

let q = new PriorityQueue(4);
q.enqueue("Hello", 3);
q.enqueue("World", 2);
q.enqueue("Foo", 8);
q.display();

出力結果

上記のコードを実行すると、次の出力が得られます。

[ { data: 'World', priority: 2 },
  { data: 'Hello', priority: 3 },
  { data: 'Foo', priority: 8 } ]

出力を見ると、要素が優先度の昇順（小さい順）できちんと並んでいることがわかります。つまり、優先度が最も高い「Foo」（8）が末尾に配置され、取り出し側の設計次第で優先度の高い要素から処理できる状態になっています。

計算量について

このenqueue関数の動作は、挿入ソートの挿入処理と同じ仕組みです。最悪の場合、配列のすべての要素を走査する必要があるため、1回の挿入にかかる時間計算量は O(n) となります。要素数が多い場合は、二分ヒープ（バイナリヒープ）を用いた実装にすることで O(log n) へ改善できるため、パフォーマンスが重要な場面では検討するとよいでしょう。