|
優先度つきキュー（ゆうせんどつき -、）は、以下の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'')。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「優先度つきキュー」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Priority queue 」があります。 スポンサード リンク
|