算法—優先隊列，

算法—優先隊列，

許多應用程序都需要處理有序的元素，但不一定要求它們全部有序，或是不一定要一次就將它們排序。很多情況下我們會收集一些元素，處理當前鍵值最大的元素，然後再收集更多的元素，再處理當前鍵值最大的元素，如此這般。

在這種情況下，一個合適的數據結構應該支持兩種操作：刪除最大元素和插入元素。這種數據類型叫做優先隊列。優先隊列的使用和隊列（刪除最老的元素）以及棧（刪除最新的元素）類似，但高效地實現它則更有挑戰性。

通過插入一列元素然後一個個地刪掉其中最小的元素，我們可以用優先隊列實現排序算法。一種名為堆排序的重要排序算法也來自於基於堆的優先隊列的實現。

API

優先隊列最重要的操作就是刪除最大元素和插入元素，

優先隊列的調用示例

為了展示優先隊列的抽象模型的價值，考慮以下問題：輸入N個字符串，每個字符串都對映著一個整數，你的任務就是從中找出最大的（或是最小的）M個整數（以及關聯的字符串）。這些輸入可能是金融事務，你需要從中找出最大的那些；或是農產品中的殺蟲劑含量，這時你需要從中找出最小的那些；在某些應用場景中，輸入量可能非常巨大，甚至可以認為輸入是無限的。解決這個問題的一種方法是將輸入排序然後從中找出M個最大的元素，但我們已經說明輸入將會非常龐大。另一種方法是將每個新的輸入和已知的M個最大元素比較，但除非M較小，否則這種比較的代價會非常高昂。只要我們能夠高效地實現insert()和delMin()，下面的優先隊列用例中調用了MinPQ的TopM就能使用優先隊列解決這個問題。在現代基礎性計算環境中超大的輸入N非常常見，這些實現使我們能夠解決以前缺乏足夠資源去解決的問題。如表所示

算法：

/**
 * 一個優先隊列的用例
 */
public class TopM {

	//打印輸入流中最大的M行
	public static void main(String[] args) {
		int M = Integer.parseInt(args[0]);
		MinPQ<Transaction> pq = new MinPQ<Transaction>(M+1);
		//為下一行輸入創建一個元素並放入優先隊列中
		while(StdIn.hasNextLine()){
			pq.insert(new Transaction(StdIn.readLine()));
			if(pq.size() > M){
				pq.delMin();//如果優先隊列中存在M+1個元素則刪除其中最小的元素
			}	//最大的M個元素都在優先隊列中

			Stack<Transaction> stack = new Stack<Transaction>();
			while(!pq.isEmpty()){
				stack.push(pq.delMin());
			}
			for (Transaction t : stack) {
				StdOut.println(t);
			}
		}
	}
}

這段代碼調用了MinPQ並會打印數字最大的M行。

【源碼下載】