算法子目录：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)