topk问题,即寻找最大的k个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.
方法一:先排序,然后截取前k个数.时间复杂度：o(n*logn)+o(k)=o(n*logn)。这种方式比较简单粗暴，提一下便是。
方法二：最大堆
我们可以创建一个大小为k的数据容器来存储最小的k个数，然后遍历整个数组，将每个数字和容器中的最大数进行比较，如果这个数大于容器中的最大值，则继续遍历，否则用这个数字替换掉容器中的最大值。这个方法的理解也十分简单，至于容器的选择，很多人第一反应便是最大堆，但是python中最大堆如何实现呢？我们可以借助实现了最小堆的heapq库，因为在一个数组中，每个数取反，则最大数变成了最小数，整个数字的顺序发生了变化，所以可以给数组的每个数字取反，然后借助最小堆，最后返回结果的时候再取反就可以了，代码如下：
import heapq
def get_least_numbers_big_data(self, alist, k):
max_heap = []
length = len(alist)
if not alist or k length:
return
k = k – 1
for ele in alist:
ele = -ele
if len(max_heap) k:
return qselect(right, k)
else:
left = [x for x in a[:-1] if x