優先度付きキュー
優先度付きキュー（ゆうせんどつきキュー、英: priority queue）は、以下の4つの操作をサポートする抽象データ型である。
- キューに対して要素を優先度付きで追加する。
- 最も高い優先度を持つ要素をキューから取り除き、それを返す。
- (オプション) 最も高い優先度を持つ要素を取り除くことなく参照する。
- (オプション) 指定した要素を取り除くことなく優先度を変更する
実装
[編集]優先度付きキューを実装する最も簡単な方法は、連想配列を用いて、それぞれの優先度に要素のリストを繋げることである。連想リストやハッシュテーブルを連想配列の実装に用いた場合は、要素の追加はO(1)であるが、要素の削除や先頭の参照にはすべてのキーを探索しなければならないのでO(n)かかる。もし、平衡2分探索木を使用した場合は、上記の3つの操作をO(log n)で行うことができる。平衡木は用意されているが、それ以上のものは用意されていない場合は、これが一般的な方法である。 Van Emde Boas treeは連想配列の一種で、上記の3つの操作をO(log log n)で行うことができるが、キューの空間コストがO(2m/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) |
応用例
[編集]- グラフのアルゴリズム - ダイクストラ法, プリム法
- バンド幅の管理
- オペレーティングシステム - プロセス処理、割り込み処理、ロードバランシング
- データ圧縮 - ハフマン符号
- 離散イベントのシミュレーション。離散イベントのシミュレーションにおいてイベントを管理することである。イベントはシミュレーションの時間を優先度としてキューに追加される。シミュレーションの実行は、繰り返しキューの先頭にある要素を取り出し、イベントを実行することで進む。
ソートとの関係
[編集]優先度付きキューからはソートを思い浮かべることができる。つまり、ソートしたい要素をすべて優先度付きキューに入れて順番に取り出せばそれはソートされている。優先度付きキューによる抽象化を取り除くと、これは実際にいくつかのソートアルゴリズムで用いられている手続きである。このソート法は以下のソートアルゴリズムと等しくなる。
- ヒープソートに等しい場合は、優先度付きキューがヒープによって実装されている場合である。
- 選択ソートに等しい場合は、優先度付きキューが整列されていない配列で実装されている場合である。
- 挿入ソートに等しい場合は、優先度付きキューが整列された配列で実装されている場合である。
