優先度つきキュー

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

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

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

実装[編集]

優先度つきキューを実装する最も簡単な方法は、連想配列を用いて、それぞれの優先度に要素のリストを繋げることである。連想リストやハッシュテーブルを連想配列の実装に用いた場合は、要素の追加は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 が標準クラスライブラリにあり、二分ヒープで実装されている。

応用例[編集]

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

ソートとの関係[編集]

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

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

関連項目[編集]

参照[編集]