優先度付きキュー

2025年10月21日

優先度付きキュー

英語表記: Priority Queue

概要

優先度付きキューは、基本的なデータ構造である「キュー」の機能を拡張した派生構造の一つです。通常のキュー（待ち行列）がデータを挿入順に取り出す先入れ先出し（FIFO: First-In, First-Out）の原則に従うのに対し、この構造は、格納されている各要素に設定された「優先度」に基づいて処理順序を決定します。つまり、最も優先度の高い要素が、挿入された順番に関係なく、最初に取り出されることが保証されるデータ構造なのです。これは、処理の重要度に応じて順番を変えたい場合に非常に役立つ仕組みだと言えますね。

詳細解説

キューの派生構造としての役割

私たちが学んでいるデータ構造の分類において、優先度付きキューは「キュー」カテゴリ内の「派生構造」として位置づけられています。なぜ標準のキューでは不十分で、この派生構造が必要になるのでしょうか。

標準のキューは、レジ待ちの列のように、公平に順番を待つ状況では完璧に機能します。しかし、コンピュータシステム内のタスク処理では、「公平性」よりも「重要性」が問われる場面が多々あります。例えば、OSが複数のアプリケーションを同時に実行する場合、ユーザーの操作に直結するタスク（キー入力など）は、バックグラウンドでのデータ圧縮タスクよりも迅速に処理されなければなりません。

優先度付きキューは、この「重要度による順序付け」を実現するために設計されました。要素をキューに格納する際、その要素が持つ優先度情報も一緒に記録します。

動作原理と主要コンポーネント

優先度付きキューの操作は、主に要素の挿入（エンキュー）と取り出し（デキュー）の2つですが、その仕組みが標準キューとは決定的に異なります。

挿入時（エンキュー）:
要素をキューに追加します。この際、要素が持つ優先度（通常は数値で表現されます。数値が大きいほど高優先度、または小さいほど高優先度、と定義されます）も格納されます。
取り出し時（デキュー）:
これが最も重要な点です。標準キューでは、最も古く挿入された要素が取り出されますが、優先度付きキューでは、現在格納されている全要素の中で、最も優先度の高い要素が選択され、取り出されます。挿入された時間軸はここでは考慮されません。

ポイント: もし複数の要素が同じ最高優先度を持っている場合はどうなるでしょうか？この場合、システムによって異なりますが、通常はそれらの要素間では挿入順（FIFO）が適用されることが一般的です。

効率的な実装方法（ヒープ構造）

優先度付きキューの機能を効率的に実現するためには、内部構造に工夫が必要です。もし、単純なリスト構造を使ってしまうと、新しい要素を取り出すたびにリスト全体をスキャンして最高の優先度を探す必要があり、非常に時間がかかってしまいます。

そこで、多くの優先度付きキューは、ヒープ構造（特に二分ヒープ）という別のデータ構造を利用して実装されます。ヒープ構造は、親ノードが子ノードよりも常に高い（または低い）優先度を持つというルールを守るツリー構造です。このヒープを用いることで、最高の優先度を持つ要素を非常に高速に（理論的には$O(1)$の時間で）特定し、取り出すことが可能になるのです。

このように、優先度付きキューは、基本的な「キュー」の概念を土台としつつ、最高の効率を求めて「ツリー」（ヒープ）の要素を取り入れた、非常に巧妙な派生構造であると言えるでしょう。

具体例・活用シーン

優先度付きキューは、コンピュータサイエンスの分野で非常に広範に利用されています。ここでは、初心者の方にも分かりやすいように、実世界の例と、コンピュータシステムでの活用シーンを挙げます。

1. 救急病院のトリアージ（メタファー）

通常のキューは、銀行の窓口のように「来た順」にサービスを提供します。しかし、救急病院の受付はそうではありません。

もし、受付に軽度の風邪の患者が5人並んでいて、その後に交通事故で重傷を負った患者が運び込まれたとしましょう。病院は「来た順（FIFO）」を無視し、重傷患者を最優先で治療室へ通します。

この病院の受付の仕組みこそが、まさに優先度付きキューの動作そのものです。

患者（要素）：処理を待っているデータやタスク。
重症度（優先度）：タスクの重要性。
トリアージ（処理）：優先度を判定し、最も高いものから取り出すデキュー操作。

この病院のトリアージシステム（優先度付きキュー）があるからこそ、命に関わる重要なタスクが遅延なく処理されるのです。データ構造（リスト, スタック, キュー, ツリー）の文脈で見ると、標準のキューが持つ公平性という美点を捨て、実用的な効率性を追求した結果生まれた、非常に重要な派生構造であることがよく理解できますね。

2. オペレーティングシステム（OS）のタスクスケジューリング

現代のOSは、多数のプログラムやプロセスを同時に実行しています。CPUの時間をどのプロセスに割り当てるかを決定するのがタスクスケジューラです。ユーザーが直接操作するフォアグラウンドのプロセスや、システムを維持するための重要なプロセスには、高い優先度が割り当てられます。タスクスケジューラは、この優先度付きキューを参照し、常に最も重要なタスクからCPU時間を割り当てて処理を進めるのです。

3. ネットワークルータのパケット処理

インターネット上でデータが送受信される際、ルータは膨大な数のデータパケットを処理します。ビデオストリーミングのようなリアルタイム性の高いデータや、制御信号のパケットは、メールのような遅延が許容されるデータよりも高い優先度で処理される必要があります。ルータ内部では、優先度付きキューを用いてパケットを管理することで、ネットワーク全体のサービス品質（QoS）を維持しています。