優先度つきキュー

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

優先度つきキュー(ゆうせんどつき -、: 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においては、コンテナアダプタの1つとして、"priority_queue"と呼ばれている。STLの本当のコンテナとは違い、イテレータによる要素へのアクセスを認めていない(ADTの定義に厳密に忠実である)。GCC (libstdc++) の実装では、アルゴリズムを色々と選べるようになっているが、デフォルトはペアリングヒープである[1]

Java[編集]

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

Java 8 現在、計算量は以下の通り[2]。優先度の変更は 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)

応用例[編集]

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

ソートとの関係[編集]

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

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

関連項目[編集]

参照[編集]