算法子目录：https://www.jianshu.com/p/02492be3c5f5
题
现在有n个数，设计算法找出前k大个数
解决思路
- 排序后切片
使用快排排序后切片，复杂度为O(nlogn+k) - “LOW B” 三人组
因为这三种排序可以通过控制外部循环决定排序次数，时间复杂度为O(kn)
相比之下，这种方法比第一种要快。 - 堆排序
最后就是堆排序，我们的主角。
使用堆排序的解决思路
- 取前K个元素组成一个小根堆，堆顶就是目前第k大的数。
- 依次向前遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将堆顶替换为该元素，并且对堆进行一次调整。
- 遍历列表所有元素后，倒序弹出堆顶。
例子：
有列表 [6,8,1,9,3,0,7,2,4,5]，取前5大的数。
这样我们就要取出前五个数，构建一个小根堆如下：
1
3 6
9 8
列表内剩余元素：0,7,2,4,5
然后将剩余元素一个一个和堆顶比较，大于堆顶则替换，小于堆顶则忽略:
元素0:0<1 忽略
元素7:7>1 替换，调整
3
7 6
9 8
元素2:2<3 忽略
元素4:4>3 替换，调整
4
7 6
9 8
元素5:5>4 替换，调整
5
7 6
9 8
最后依次弹出堆顶：[5,7,6,9,8]
复杂度为O(klogk+(n-k)logk)=O(nlogk)。
代码如下：
def sift(li,low,high):
#li表示树，low表示high的父节点，high表示树的最后一个节点
tmp = li[low]
i = low
j = 2 * i + 1 #初始j指向左子节点
# i 指向空位，j指向子节点
while j <= high: #退出的第二种情况：j大于high，说明空
if j + 1 <= high and li[j] < li [j+1]:#如果右子节点存在，且大于左子节点
j += 1 #则使用右子节点
if li[j] > tmp:
#这里比较 li[j] 与 li[j] 的父节点 li[i] 的大小，如果 li[j] 大于 li[i] ，则交换。
li[i] = li[j]
# 同时，让i保存j的位置，j再保存相应的左子节点。 接着到while进行判断 j还在不在堆的范围中。
i = j
j = 2 * i + 1
else: #退出的第一种情况：j的位置比tmp小，说明两个子节点都比tmp小。
break
li[i] = tmp #把拿出来的那个值放在空位上面。
def topk(li,k):
heap = li[0:k]
for i in range(k//2-1,-1,-1):
sift(heap,i,k-1)
for i in range(k,len(li)):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap,0,k-1)
for i in range(k-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
sift(heap,0,i-1)
