你的位置:首页 > 操作系统

[操作系统]算法—优先队列


许多应用程序都需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。很多情况下我们会收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键值最大的元素,如此这般。

在这种情况下,一个合适的数据结构应该支持两种操作:删除最大元素和插入元素。这种数据类型叫做优先队列。优先队列的使用和队列(删除最老的元素)以及栈(删除最新的元素)类似,但高效地实现它则更有挑战性。

通过插入一列元素然后一个个地删掉其中最小的元素,我们可以用优先队列实现排序算法。一种名为堆排序的重要排序算法也来自于基于堆的优先队列的实现。

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行。

 

源码下载