|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 優 ： [ゆう] 1. (adj-na,n) actor 2. superiority 3. gentleness ・ 優先 ： [ゆうせん] 1. (n,vs) preference 2. priority ・ 優先順位 ： [ゆうせんじゅんい] (n) priority ・ 先 ： [せん] 1. (n,adj-no) the future 2. priority 3. precedence 4. former 5. previous 6. old 7. late ・ 順 ： [じゅん] 1. (adj-na,n,n-suf) order 2. turn ・ 順位 ： [じゅんい] 【名詞】 1. order 2. rank 3. precedence ・ 位 ： [くらい] 1. (n,n-adv,suf,vs) grade 2. rank 3. court order 4. dignity 5. nobility 6. situation 7. throne 8. crown 9. occupying a position 10. about 1 1. almost 12. as 13. rather 14. at least 15. enough to 1 ・ 付 ： [ふ] 1. (n,vs) giving to 2. submitting to 3. refer to 4. affix 5. append ・ 付き ： [つき, づき] 1. (n,n-suf) attached to 2. impression 3. sociality 4. appearance 5. furnished with 6. under 7. to ・ 待ち ： [まち] 1. (n,n-suf) waiting 2. waiting time ・ 行 ： [くだり, ぎょう] 【名詞】 1. (1) line 2. row 3. (2) verse ・ 行列 ： [ぎょうれつ] 1. (n,vs,n) (1) line 2. procession 3. (2) (gen) (math) matrix ・ 列 ： [れつ] 【名詞】 1. queue 2. line 3. row
優先度つきキュー（ゆうせんどつき -、）は、以下の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 」があります。 スポンサード リンク
|