数据结构与算法（二） 优先队列
一、优先队列的基本概念
我们的电脑总是运行着多个程序，电脑会给每个程序分配一个优先级，并首先执行下一个优先级更高的程序。在此情况下，可将其抽象为一个数据结构，该数据结构支持 删除最大元素和 插入元素的操作，这种数据结构叫 优先队列。通过插入一列元素并逐个删除最小元素，可以使用优先队列来对数据进行排序。
| public class MaxPQ<Key extends Comparable> | |
|---|---|
| MaxPQ | 创建一个优先队列 |
| MaxPQ(int max) | 创建一个最大容量为max的优先队列 |
| MaxPQ(Key[] a) | 用数组a[]中的元素创建一个优先队列 |
| void insert(Key v) | 向优先队列中插入一个元素 |
| Key Max() | 返回最大元素 |
| Key delMax() | 删除并返回最大元素 |
| boolean isEmpty() | 返回优先队列是否为空 |
| int size() | 返回优先队列中元素的个数 |
考虑一个问题：输入N个字符串，每个字符串都对应着一个数字，现要求从中找出最大的M个整数，解决该问题的一个方法是将每个新的输入和已知的M个最大的值进行比较，此时，除非M较小，否则开销会非常大。
以下是从N个数中找出最大的M个数的不同算法的成本：
下面是一个优先队列的示例：
public class TopM{public static void main(String[] args){//打印输入流中最大的M行int M=Integer.parseInt(args[0]);MinPQ<Transaction> pq= new MinPQ<Transaction>(key);while(StdIn.hasNextLine()){//为下一行创建一个元素并放入优先队列中pq.inset(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.printIn(t);}}
}
上述代码从命令行输入一个数字M及一系列字符串，每一行表示一个事务，改代码会打印最大的M行启用到了Transaction类，构造了一个用数字作为键的优先队列，当优先队列的大小超过M时，会删除最小的元素，所有事务输入完毕后，会从中从小到大顺序打印出最大的M个事务。
