一、引入

问题：目前共有n个数，设计算法得到前k大的数。（m<n）

解决思路：

1. 排序后切片：O(n*logn+m) = O(n*logn)
2. 排序LowB三人组：O(mn)  例如冒泡排序，交换m次，即可取前m大的数字；对于插入排序，维护一个长度为100的列表，将其排好序，再依次遍历其他数，将插入的数字放入其中，后面的数字往后挪；选择排序我们选择100次。
3. 堆排序：O(nlogk)

二、堆排序解决思路

1. 取列表前k个元素建立一个小根堆（从小到大），其堆顶就是目前第K大的元素。
2. 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整。
3. 最后能确保小根堆是我们需要的前K大的数。
4. 遍历列表的所有元素后，倒序（因为是小根堆）弹出列表。

示例代码如下：

import random


# 调整为小根堆
def sift(li, low, high):  # 向下调整函数；初始条件应该为除了根节点，下面的子堆默认为有序的
    i = low  # i最开始指向根节点
    j = 2 * i + 1  # 左孩子
    tmp = li[low]  # 将堆顶元素存起来
    while j <= high:  # 只要j上面有数，没跑到结构外
        if j + 1 <= high and li[j + 1] < li[j]:  # 存在右孩子，且右孩子比左孩子大；不能交换
            j = j + 1  # j指向有孩子
        if li[j] < tmp:
            li[i] = li[j]  # 换数
            i = j  # 往下看一层
            j = 2 * i + 1
        else:  # 此时tmp更大，将tmp放回原位
            li[i] = tmp
            break  # 直接退出，因为sift默认下面就是堆的情况下
    else:  # 两种退出循环的条件；当其越界
        li[i] = tmp


def topk(li, k):
    heap = li[0:k]
    # 1.取前K个元素构建小根堆
    for i in range((k - 2) // 2, -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)
    return heap


li = [i for i in range(1000)]
random.shuffle(li)
print(li)
print(topk(li, 10))

输出结果如下：