topk问题

从一群数中取出前k高或者低的数。（就好比要做一个像csdn热度榜一样的东西）

堆的基础知识：【python】堆排序-CSDN博客

堆排序解决思路

1.先用列表的k个元素构建一个小根堆，小根堆最上面的元素就是最小的元素

2.依次拿列表后面的数与堆顶比较

3.如果大就替换，如果小就下一个

4.最后这个小根堆就是列表中最大的前k个数，全部提出来就可以

小根堆向下调整代码

def sort(li, up, dn):'''本函数用于堆的向下调整:param li:列表:param up: 堆顶的数:param dn: 列表最右边的数:return:'''i = up  # 定义父节点索引c = 2 * i + 1  # 定义子节点索引top = li[i]  # 储存最上方的索引while c <= dn:  # 如果有子节点if c + 1 <= dn and li[c + 1] < li[c]:  # 如果有右子节点而且比左节点小c = c + 1  # 把子节点索引定义到右节点if li[c] < top:  # 如果子节点小于该节点li[i] = li[c]  # 把子节点放到上面i = c  # 继续向下看c = 2 * i + 1else:  # 如果不比子节点小li[i] = top  # 直接放到这里breakelse:  # 如果没有子节点了li[i] = top  # 直接放下return li

主代码

def dui_topk(li,k):#截取前k个数heap=li[0:k]#对这k个数构建一个小根堆for i in range((k-2)//2,-1,-1):sort(heap,0,k-1)#后面的数依次带入进行比较for i in range(k,len(li)):if li[i]>heap[0]:heap[0]=li[i]sort(heap,0,k-1)#挨个出数for i in range(k-1,-1,-1):heap[i],heap[0]=heap[0],heap[i]sort(heap,0,i)return heap

结果实例：