一，優(yōu)先隊列
在決定病人接受治療的次序時胧砰，除了他們到達醫(yī)院的先后次序煮岁，更主要的將取決于病情的嚴重程度屉符。由這類問題可以抽象出本章將要討論的優(yōu)先隊列（Priority queue）結構。這一結構在很多應用領域都可以派上大用場良哲，比如各種事件隊列的模擬盛卡、操作系統(tǒng)中多任務的調度及中斷機制、采用詞頻調整策略的輸入法等筑凫。另外滑沧，優(yōu)先隊列也是很多高級算法的基礎，比如Huffman編碼巍实、堆排序算法都要利用優(yōu)先隊列滓技，而在采用空間掃描策略的算法中，優(yōu)先隊列是組織事件隊列的最佳形式蔫浆。
優(yōu)先隊列之所以具有廣泛的用途殖属，是得益于其高效率以及實現(xiàn)的簡捷性。正如我們將要看到的瓦盛，如果基于堆來實現(xiàn)優(yōu)先隊列洗显，則其初始化構造可以在線性時間內完成外潜，而每次插入或刪除操作都可以在O(logn)的時間內完成。
二挠唆，關鍵碼
正如醫(yī)院根據病情嚴重程度確定病人接受治療的次序一樣处窥，優(yōu)先隊列中各對象之間的次序是由它們共同的某個特征、屬性或指標決定的玄组，我們稱之為“關鍵碼”（Key）滔驾。關鍵碼本身也是一個對象。
實際上俄讹，作為優(yōu)先隊列的一個基本要求哆致，在關鍵碼之間必須能夠定義某種全序關系（Total orderrelation）。具體來說患膛，任何兩個關鍵碼都必須能夠比較大小摊阀，也就是滿足以下三條性質：
- 自反性：對于任一關鍵碼k，都有k ≤ k
- 反對稱性：若k1 ≤ k2 且k2 ≤ k1踪蹬，則k1 = k2
- 傳遞性：若k1 ≤ k2 且k2 ≤ k3胞此，則k1 ≤ k3
不難證明，具有以上性質的關系實際上就是所有對象之間的一個線性次序跃捣。
三漱牵，條目與比較器
在給出優(yōu)先隊列的具體定義之前，還有兩個問題有待明確：
- 在優(yōu)先隊列中疚漆，如何記錄和維護各對象與其關鍵碼之間的關聯(lián)關系酣胀？
- 如何具體實現(xiàn)上面提出的全序關系，從而通過對象的比較能夠找出其中的最小者愿卸？
為了解決這兩個問題灵临，下面我們需要分別構造出條目和比較器這兩個類。
** 3.1 條目 **
所謂一個條目（Entry）趴荸，就是由一個對象及其關鍵碼合成的一個對象（面向對象程序設計的一種典型技巧??合成模式）儒溉，它反映和記錄了二者之間的關聯(lián)關系。這樣发钝，通過將條目作為優(yōu)先隊列的元素顿涣，即可記錄和維護原先對象與其關鍵碼之間的關聯(lián)關系。
定義條目的接口：
package dsa.PriorityQueue;
/*
* 條目接口
*/
public interface Entry {
// 取條目的關鍵碼
public Object getKey();
// 修改條目的關鍵碼酝豪，返回此前存放的關鍵碼
public Object setKey(Object k);
// 取條目的數據對象
public Object getValue();
// 修改條目的數據對象涛碑，返回此前存放的數據對象
public Object setValue(Object v);
}
默認條目類的實現(xiàn)：
package dsa.PriorityQueue;
/*
* 默認條目
*/
public class EntryDefault implements Entry {
protected Object key;
protected Object value;
/**************************** 構造函數 ****************************/
public EntryDefault(Object k, Object v) {
key = k;
value = v;
}
/**************************** Entry接口方法 ****************************/
// 取條目的關鍵碼
public Object getKey() {
return key;
}
// 修改條目的關鍵碼，返回此前存放的關鍵碼
public Object setKey(Object k) {
Object oldK = key;
key = k;
return oldK;
}
// 取條目的數據對象
public Object getValue() {
return value;
}
// 修改條目的數據對象孵淘，返回此前存放的數據對象
public Object setValue(Object v) {
Object oldV = value;
value = v;
return oldV;
}
}
** 3.2 比較器 **
后一個問題似乎更難解決??畢竟蒲障，與C++之類的語言不同，Java 并不支持對比較操作符（">"、"<"或"=="等）的重載揉阎。
既然如此庄撮，不如基于Comparator 接口專門實現(xiàn)一個獨立于關鍵碼之外的比較器類，由它來確定具體的比較規(guī)則毙籽。在創(chuàng)建每個優(yōu)先隊列時洞斯，只要指定這樣一個比較器對象，即可按照該比較器確定的規(guī)則坑赡，在此后進行關鍵碼的比較烙如。這一策略的另一優(yōu)點在于，一旦不想繼續(xù)使用原先的比較器對象毅否，可以隨時用另一個比較器對象將其替換掉亚铁，而不用重寫優(yōu)先隊列本身。
定義Comparator接口：
package dsa.PriorityQueue;
/*
* 比較器接口
*/
public interface Comparator {
public int compare(Object a, Object b);// 若a>（=或<）b螟加，返回正數刀闷、零或負數
}
默認情況下，我們將使用如下比較器：
package dsa.PriorityQueue;
/*
* Comparable對象的默認比較器
*/
public class ComparatorDefault implements Comparator {
public ComparatorDefault() {
}
public int compare(Object a, Object b) throws ClassCastException {
return ((Comparable) a).compareTo(b);
}
}
四仰迁，優(yōu)先隊列ADT
優(yōu)先隊列 Q 基本操作
| 操作方法 | 功能描述 |
|---|---|
| getSize() | 返回Q 的規(guī)模 輸入：無 輸出：整數 |
| isEmpty() | 判斷Q 是否為空 輸入：無 輸出：布爾標志 |
| getMin() | 若Q 非空，則返回其中的最小條目（并不刪除） 輸入：無 輸出：條目 |
| insert(k, obj) | 將對象obj 與關鍵碼k 合成一個條目顽分，將其插入Q 中徐许，并返回該條目 輸入：一個對象及一個關鍵碼 輸出：條目 |
| delMin() | 若Q 非空，則從其中摘除關鍵碼最小的條目卒蘸，并返回該條目雌隅；否則，報錯 輸入：無 輸出：條目 |
insert()和delMin()則是優(yōu)先隊列特有的方法缸沃。需要強調的是恰起，** 這里允許在同一優(yōu)先隊列中出現(xiàn)具有相同關鍵碼的多個條目。**
五趾牧，優(yōu)先隊列java實現(xiàn)
定義接口：
package dsa.PriorityQueue;
/*
* 優(yōu)先隊列接口
*/
public interface PQueue {
// 統(tǒng)計優(yōu)先隊列的規(guī)模
public int getSize();
// 判斷優(yōu)先隊列是否為空
public boolean isEmpty();
// 若Q非空检盼，則返回其中的最小條目（并不刪除）;否則，報錯
public Entry getMin() throws ExceptionPQueueEmpty;
// 將對象obj與關鍵碼k合成一個條目翘单，將其插入Q中吨枉，并返回該條目
public Entry insert(Object key, Object obj)
throws ExceptionKeyInvalid;
// 若Q非空，則從其中摘除關鍵碼最小的條目哄芜，并返回該條目貌亭；否則，報錯
public Entry delMin() throws ExceptionPQueueEmpty;
}
其中ExceptionPQueueEmpty和ExceptionKeyInvalid意外錯的定義：
package dsa.PriorityQueue;
/*
* 當試圖對空的優(yōu)先隊列應用getMin()或delMin()方法時认臊，本意外將被拋出
*/
public class ExceptionPQueueEmpty extends RuntimeException {
public ExceptionPQueueEmpty(String err) {
super(err);
}
}
package dsa.PriorityQueue;
/*
* 當試圖使用非法關鍵碼時圃庭，本意外將被拋出
*/
public class ExceptionKeyInvalid extends RuntimeException {
public ExceptionKeyInvalid(String err) {
super(err);
}
}
基于有序（非升）列表實現(xiàn)的優(yōu)先隊列：
package dsa.PriorityQueue;
import dsa.List.List;
import dsa.List.List_DLNode;
import dsa.Sequence.Sequence;
import other.Position;
/*
* 基于有序（非升）列表實現(xiàn)的優(yōu)先隊列
*/
public class PQueue_SortedList implements PQueue {
private List L;
private Comparator C;
// 構造方法（使用默認比較器）
public PQueue_SortedList() {
this(new ComparatorDefault(), null);
}
// 構造方法（使用指定比較器）
public PQueue_SortedList(Comparator c) {
this(c, null);
}
// 構造方法（使用指定初始元素）
public PQueue_SortedList(Sequence s) {
this(new ComparatorDefault(), s);
}
// 構造方法（使用指定比較器和初始元素）
public PQueue_SortedList(Comparator c, Sequence s) {
L = new List_DLNode();
C = c;
if (null != s)
while (!s.isEmpty()) {
Entry e = (Entry) s.removeFirst();
insert(e.getKey(), e.getValue());
}
}
// 統(tǒng)計優(yōu)先隊列的規(guī)模
public int getSize() {
return L.getSize();
}
// 判斷優(yōu)先隊列是否為空
public boolean isEmpty() {
return L.isEmpty();
}
// 若Q非空，則返回其中的最小條目（并不刪除）;否則，報錯
public Entry getMin() throws ExceptionPQueueEmpty {
if (L.isEmpty())
throw new ExceptionPQueueEmpty("意外：優(yōu)先隊列空");
return (Entry) L.last();
}
// 將對象obj與關鍵碼k合成一個條目剧腻，將其插入Q中拘央，并返回該條目
public Entry insert(Object key, Object obj) throws ExceptionKeyInvalid {
Entry entry = new EntryDefault(key, obj);// 創(chuàng)建一個新條目
if (L.isEmpty()// 若優(yōu)先隊列為空
|| (0 > C.compare(((Entry) (L.first().getElem())).getKey(), entry.getKey())))
// 或新條目是當前最大者
L.insertFirst(entry);// 則直接插入至表頭
else {// 否則
Position curPos = L.last();// 從尾條目開始
while (0 > C.compare(((Entry) (curPos.getElem())).getKey(), entry.getKey()))
curPos = L.getPrev(curPos);// 不斷前移，直到第一個不小于entry的條目
L.insertAfter(curPos, entry);// 緊接該條目之后插入entry
}
return (entry);
}
// 若Q非空恕酸，則從其中摘除關鍵碼最小的條目堪滨，并返回該條目；否則蕊温，報錯
public Entry delMin() throws ExceptionPQueueEmpty {
if (L.isEmpty())
throw new ExceptionPQueueEmpty("意外：優(yōu)先隊列空");
return (Entry) L.remove(L.last());
}
}
