|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 優 ： [ゆう] 1. (adj-na,n) actor 2. superiority 3. gentleness ・ 優先 ： [ゆうせん] 1. (n,vs) preference 2. priority ・ 先 ： [せん] 1. (n,adj-no) the future 2. priority 3. precedence 4. former 5. previous 6. old 7. late ・ 先度 ： [せんど] (n-adv,n-t) recently ・ 度 ： [ど] 1. (n,n-suf) (1) degree (angle, temperature, scale, 2. (2) counter for occurrences 3. times 4. (3) strength (of alcohol) 5. (4) (uk) (pref) very 6. totally ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
優先度つきキュー（ゆうせんどつき -、）は、以下の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）』 ■ウィキペディアで「優先度つきキュー」の詳細全文を読む スポンサード リンク
|