優先度つきキュー (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: 未ソートのリスト
2. Sorted List: ソート済みのリスト
3. Special List: x.priorityの最高値が相対的に低い場合（１〜１０など）
4. 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」