優先度つきキュー (Chapter 6)

優先度つきキューとは、その名の通り優先順位がついているキューのことです。英語版
用途としては、

• ジョブ管理システム
• 印刷の順番
• event-driven simulation

オブジェクト##

全ての x ∈ S に優先度がついており、x.priorityが存在する。
優先度つきキューはFIFO (first in first out) に限定していないので応用が利く。

オペレーション##

• Insert(S,x)
  • xの値をSに追加する
  • 返り値はvoid
• Max(S)
  • x.priorityの最大値を返す
• Extract_max(S)
  • x.priorityの最大値を返す
  • x.priorityの最大値をSから削除する
• Increment_priority(S, x, k)
  • x.priorityの値をkに設定する
  • k > x.priority
  • xの設定を更新する

List##

1. Unsorted List: 未ソートのリスト

• Sorted List: ソート済みのリスト
• Special List: x.priorityの最高値が相対的に低い場合（１〜１０など）
• Heap：バイナリヒープの事をさす、特に最大二分木の事をさす。特にMin-Heapが優先度つきキューの実装に使われる。

データ構造##

| Insert | Max| Extract_Max(削除の部分）|Increment_priority
------------ | -------------| -------------|-------------|-------------
Unsorted List | O(1)|O(n)|O(1)|O(1)
Sorted List | O(n)|O(1)|O(1)|O(n)
Special List| O(1)|O(k)|O(1)|O(n)
Heap | O(log(n))|O(1)|O(log(n))|O(log(n))

参考文献目録##

主にCormenら著書「Introduction to Algorithm」