Pro1:寻找前K大数
方法1：K小根堆 后面的值若大于当前根，则替换之，并调整堆
大部分人都推荐的做法是用堆，
小根堆
。下面具体解释下:
如果K = 1，那么什么都不需要做，直接遍历一遍，时间复杂度O（N）。
下面讨论K 比较大的情况，比如1万。
建立一个小根堆，则根是当前最小的第K个数。然后读入N-K个数，
每次读入一个数就与当前的根进行比较，如果大于当前根，则替换之，并调整堆
。如果小，则读入下一个。
时间复杂度
O
（
N*logK
）。
方法2：利用快排分区思想：
本题还有一个时间复杂度比较好的做法。在编程之美上提到过该算法。
首先
找到最大的第
K
个数
。这个时间复杂度可以做到
O
（
N
）
，具体做法如下（利用快排分区思想）：
从N个数中随机选择一个数，扫描一遍，
比
n
大的放在右边，
r
个元素，比
n
小的放左边，
l
个元素
如果： a：l = K-1 返回n
b：l > K-1 在l个元素中继续执行前面的操作。
c：l < K-1 在r个元素中继续执行前面的操作。
b,c每次只需执行一项，因此
平均复杂度
大概为
：
O(n+n/2+n/4…)=O(2n)=O(n)
Pro2: K路合并求Top-K
20路已经有序，20路合并 求Top500
有 20 个数组，每个数组有 500 个元素，并且是有序排列好的，现在在这 20*500个数中找出排名前 500 的数。
答：
从
20
个数组中各取一个数，并记录每个数的来源数组，
建立一个含
20
个元素的大根堆
。此时堆顶就是最大的数，取出堆顶元素，并
从堆顶元素的来源数组中取下一个数加入堆
，再取最大值，一直这样
进行
500
次即可
。
Pro3: K路合并排序
请给出一个时间为O(nlgk)、用来
将
k
个已排序链表合并为一个排序链表
的算法，此处n为所有输入链表中元素的总数。
算法思想:
1. 从k个链表中取出每个链表的第一个元素，
组成一个大小为
k
的数组
arr
，然后将数组
arr
转换为最小堆，那么
arr[0]
就为最小元素了；
2.
取出
arr[0]
，将其放到新的链表中，然后将
arr[0]
元素在原链表中的下一个元素补到
arr[0]
处，即
arr[0].next
，如果 arr[0].next为空，
即它所在的链表的元素已经取完了，那么将堆的最后一个元素补到
arr[0]
处，
堆的大小自动减
1
，
循环即可。
http://www.programlife.net/stl-priority-queue.html
Pro4: 整体有序局部无序问题
一个有100亿个元素的整型数组，它的
元素是有序的
，现在把它分成若干段，每段不超过20个元素，每段的元素个数不等，现在在
每段内将这些元素的顺序打乱
，然后
重新
将这100亿个元素的数组排序，请问时间复杂度最小的算法是什么？并给出时间复杂度。
http://bbs.csdn.net/topics/390252481
http://blog.csdn.net/burningsheep/article/details/8104493
分析：
如果每段长度相等，则可以考虑采用上面的K路归并
，但此处长度不相等，需另行考虑其它方法。
解：（直接插入排序）
假设第1到第5n个数已经有序为sort(5n)，那么我们要将5n+1到5n+5这5个数据添加到已排序的数组中，只需要进行插入排序，将这5个数添加进即可。由于分段的长度不超过5，所以第5n+1个数在插入的时候，最多只需要搜索到第5n-4个数就可以了，比较个数不会超过5次。又因为5n+1到5n+5是已经排好序的，所以，后面的数比较次数也不会超过5次（最多比较到前一个插入的位置）。因此，
每加入
5
个数到已排序数组中，时间复杂度是
O
（
5*5
），
假设长度为N，每段长不超过K。则每段插入的时间复杂度即为
O
（
K*K
）。
而对于以段为单位插入的操作，需要进行N/K次，所以，总的时间复杂度是
O(K*K)*O(N/K)=O(NK)
Pro5:100亿个数，求最大的1万个数，并说出算法的时间复杂度
建一个堆,先把最开始的1万个数放进去。以后每进一个,都把最小的赶出来。
上述算法的可选实现工具：自己建立数组进行堆排序、使用优先队列priority_queue、使用集合set multiset
在最大堆中，根结点的值总是大于它的子树中任意结点的值。于是我们每次可以在O(1)得到已有的k个数字中的最大值18，但需要O(logk)时间完成删除以及插入操作。
队列(queue)维护了一组对象，进入队列的对象被放置在尾部，下一个被取出的元素则取自队列的首部。priority_queue特别之处在于，允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部，而是放在比它优先级低的元素前面。优先队列有两种，一种是最大优先队列；一种是最小优先队列；每次取自队列的第一个元素分别是优先级最大和优先级最小的元素。
在STL中set和multiset都是基于红黑树实现的，查找、删除和插入操作都只需要O(logk)。