本文共 1583 字，大约阅读时间需要 5 分钟。

topk问题(取出前k大或小的数)

    在我的上一篇博客中，我们讲了怎么利用堆进行排序，即堆排序。这节来说说topk问题, 即:现在有n个数，设计算法得到前k大的数(k<n).

1. 排序后切片 O(nlog(n))
2. 排序LOWB三人组 O(kn)
3. 堆排序 O(nlog(k))

今天讲讲方法3:

1. 取列表前k个元素建立一个小根堆，堆顶就是目前第k大的数
2. 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素;
   如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整；
3. 遍历列表所有元素后，倒序弹出堆顶。

演示视频:

代码

'''TOP: topkauthor: Bluetime: 2020-08-05QQ: 2458682080'''# 堆排序没有递归# 针对小根堆的调整函数def sift(li, low, high):    """    :param li: 列表    :param low: 堆的堆顶位置    :param high: 堆的最后一个元素的位置    :return:    """    i = low   # i最开始指的是根结点    j = 2 * i + 1   # j开始是左孩子    temp = li[low]   # 把堆顶存起来    while j <= high:   # 只要j位置有节点        if j+1 <= high and li[j+1] < li[j]:  # 如果右孩子有且比较大            j += 1    # j指向右孩子        if li[j] < temp:            li[i] = li[j]            i = j     # 往下看一层            j = 2 * i + 1        else:         # temp更大，把temp放到i的位置上            li[i] = temp   # 把temp放到某一级领导的位置上            break    else:        li[i] = temp    # 把temp放到叶子节点上# topk问题def topk(li, k):    # 1. 建堆    heap = li[0:k]  # 先把列表索引0到k的数取出来(取列表前k个数)，进行建堆    for i in range((k-2)//2, -1, -1):        sift(heap, i, k-1)    # 2. 遍历    for i in range(k, len(li)-1):   # 从k开始        if li[i] > heap[0]:  # 比较li[i]和堆顶的元素的大小，如果大于堆顶，则替换堆顶，并做一次调整，如果小于堆顶，则舍弃这个li[i]            heap[0] = li[i]            sift(heap, 0, k-1)    # 3. 出数    for i in range(k - 1, -1, -1):        # i指向当前堆的最后一个元素        heap[0], heap[i] = heap[i], heap[0]        sift(heap, 0, i - 1)  # i-1是新的high    return heapimport randomli = list(range(1000))random.shuffle(li)print(topk(li, 10))

结果为:

[999, 998, 997, 996, 995, 994, 993, 992, 991, 990]

转载地址：http://rfiwi.baihongyu.com/