找出m个数中最小的n个数的算法

核心提示：这个问题属于常见问题了，我的办法是采用堆，找出m个数中最小的n个数的算法，截取STL中的partial_sort算法的实现：template <class RandomAccessIterator, class T, class Compare>void __partial_sort(RandomAcces

这个问题属于常见问题了，我的办法是采用堆。

截取STL中的partial_sort算法的实现：

template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
　　RandomAccessIterator last, T*, Compare comp) {
　 make_heap(first, middle, comp);
　 for (RandomAccessIterator i = middle; i < last; ++i)
　　　 if (comp(*i, *first))
　　　　　 __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
　 sort_heap(first, middle, comp);
}

上面这个函数是对一个序列进行部分排序，排序之后，在first，middle之间的元素有序。

它的做法首先将原始的first，middle中的数据生成一个堆，然后遍历之后的数据，如果比前面的元素中最大的元素大，就把最小的元素删除插入这个新的元素，这个过程是lg(middle - first），最后进行堆排序。

不是每个元素都需要重新调整堆，所以最坏的情况时间复杂度是n * lg(middle - first)。

类似的，可以根据这个算法并且使用堆算法解决这个问题，如上所言，最坏的时间复杂度是n * lg(m)，其中n是元素总量，m是待查找的最大的m个数。

根据我上面的这个想法， 还有我原来写过的堆算法，给出解决这个问题的代码，由于我原来写的堆算法是大项堆(max-heap)，也就是堆中最大的元素在根部，所以这里面求出来的是数中最小的10个数，如果要求最大的10个数，要讲这个堆改成小项堆，其实也就是改变堆中父子之间的大小关系罢了，其他的地方不变。