在一百万数字中求最大的10个数字的算法

基于堆的优先队列实现

优先队列严格说实际上不是一种队列，因为它并不需要遵循队列的FIFO特性，而要求的基本操作包括：向队列中插入新的记录，以及移出队列中的最大的元素。我们可以以各种不同的方式来实现优先队列——只要能够满足上面的两个接口就可以了。但是基于堆的优先队列则具有较好的性能。

优先队列是一种很有用的数据结构，因为实际上我们不是每时每刻都需要对数据进行严格的排序，有时候我们仅仅能够获得最大的元素的即可，但是如果以顺序查找的方式实现的话，效率上根本满足不了要求。而堆则提供了一种较高效率的实现策略。

网上看到一个面试题（据说是ATC的）：写一个在一百万数字中求最大的10个数字的算法。这个问题的解决方案很多，显然考察的是算法的效率（因为基数一百万）。至少有以下几种解法：1）冒泡10次；2）用一个10个大小的数组保存最初10个元素，然后遍历，遇到比最小的大的元素就插入这个数组中，并去掉最小的元素。显然这两种解法的效率都不是特别合适。基于堆的算法应该是提供了一个较好的解决方案，构建大顶堆，取得第一个元素，然后循环10次即可达到题目要求。当然，直接使用基于堆的优先队列可以达到同样的目的。