優先度付きキュー

優先度付きキュー（ゆうせんどつきキュー、英: priority queue）は、以下の4つの操作をサポートする抽象データ型である。

• キューに対して要素を優先度付きで追加する。
• 最も高い優先度を持つ要素をキューから取り除き、それを返す。
• (オプション) 最も高い優先度を持つ要素を取り除くことなく参照する。
• (オプション) 指定した要素を取り除くことなく優先度を変更する

実装

優先度付きキューを実装する最も簡単な方法は、連想配列を用いて、それぞれの優先度に要素のリストを繋げることである。連想リストやハッシュテーブルを連想配列の実装に用いた場合は、要素の追加はO(1)であるが、要素の削除や先頭の参照にはすべてのキーを探索しなければならないのでO(n)かかる。もし、平衡2分探索木を使用した場合は、上記の3つの操作をO(log n)で行うことができる。平衡木は用意されているが、それ以上のものは用意されていない場合は、これが一般的な方法である。 Van Emde Boas treeは連想配列の一種で、上記の3つの操作をO(log log n)で行うことができるが、キューの空間コストがO(2^m/2)かかる。ここで、mは優先度を表現するために必要なビット数である。

上記のアプローチよりも性能がよかったり、より多くの操作を提供するヒープデータ構造は多い。

• 二分ヒープは要素の挿入・削除をO(log n)で、先頭の参照はO(1)で行うことができる。
• 二項ヒープはいくつかの操作を追加するが、先頭の参照にO(log n)かかる。
• フィボナッチヒープは要素の挿入、先頭の参照、プライオリティを下げる操作にO(1)の償却実行時間 (amortized time) で、要素の削除はO(log n)。

C++

STLにはコンテナアダプタとしてpriority_queueが存在する。同じ優先度を持つ2要素の順番は定義されていない。C++の抽象データ型の定義に準拠しているが、イテレータによる要素へのアクセスを認めていないため、コンテナとしての要件は満たさない。実装はコンパイラ依存であり、GCC (libstdc++-v3)では二分ヒープが採用されている^[1]。

g++拡張のPBDSには内部データ構造を選択可能なpriority_queueが存在し、デフォルトはペアリングヒープである^[2]。

Java

java.util.PriorityQueue が標準クラスライブラリにあり、二分ヒープで実装されている。

Java 8 現在、計算量は以下の通り^[3]。優先度の変更は API が無いので 先頭以外の削除 → 追加 で実装できるが、先頭以外の削除が一般的な二分ヒープよりも計算量が多いことに注意。ダイクストラ法などで使う場合は違う実装を使った方が良い。

計算量

操作	メソッド名	最悪計算量	平均計算量
先頭の参照	peek	O(1)	O(1)
要素数の取得	size	O(1)	O(1)
追加	add	O(log n)	O(1)
先頭の削除	poll	O(log n)	O(log n)
先頭以外の削除	remove(Object)	O(n)	O(n)
優先度の変更	存在せず	O(n)	O(n)

応用例

• グラフのアルゴリズム - ダイクストラ法, プリム法
• バンド幅の管理
• オペレーティングシステム - プロセス処理、割り込み処理、ロードバランシング
• データ圧縮 - ハフマン符号
• 離散イベントのシミュレーション。離散イベントのシミュレーションにおいてイベントを管理することである。イベントはシミュレーションの時間を優先度としてキューに追加される。シミュレーションの実行は、繰り返しキューの先頭にある要素を取り出し、イベントを実行することで進む。

ソートとの関係

優先度付きキューからはソートを思い浮かべることができる。つまり、ソートしたい要素をすべて優先度付きキューに入れて順番に取り出せばそれはソートされている。優先度付きキューによる抽象化を取り除くと、これは実際にいくつかのソートアルゴリズムで用いられている手続きである。このソート法は以下のソートアルゴリズムと等しくなる。

• ヒープソートに等しい場合は、優先度付きキューがヒープによって実装されている場合である。
• 選択ソートに等しい場合は、優先度付きキューが整列されていない配列で実装されている場合である。
• 挿入ソートに等しい場合は、優先度付きキューが整列された配列で実装されている場合である。

関連項目

• アルゴリズム
• データ構造