什么是topk问题

Top-k 问题是指在一个元素集合中找出前 k 个最大或最小的元素。这个问题在很多实际场景中都有应用，例如在大数据处理中获取最大的 k 个元素、搜索引擎中的搜索结果排序等。

解决方法

堆排序：使用最小堆或最大堆来解决 Top-k 问题是一种常见的方法。初始时，将前 k 个元素构建成一个最小堆或最大堆。然后遍历剩余的元素，如果当前元素比堆顶元素大（或小），则将堆顶元素替换为当前元素，并重新调整堆使其满足堆的性质。最终，堆中的元素就是前 k 个最大（或最小）的元素。
快速选择算法：快速选择算法是基于快速排序的思想，它可以在平均情况下快速找到第 k 小（或第 k 大）的元素。快速选择算法选择一个枢轴元素，将序列分为两部分，一部分比枢轴元素小，另一部分比枢轴元素大。根据枢轴元素的位置，可以确定第 k 小（或第 k 大）元素在哪个部分中，然后递归地在相应的部分中查找。这样，可以通过不断缩小问题规模来找到前 k 个最大（或最小）的元素。

无论是使用堆排序还是快速选择算法，它们的时间复杂度都是 O(n log k)，其中 n 是元素集合的大小。这是因为在找出前 k 个最大（或最小）元素时，需要进行 k 次堆调整或划分操作。这使得这两种方法在处理大规模数据时具有较高的效率。

代码示例（堆排序）

在上一章笔记中已经介绍过堆排序的算法原理，这里直接进行应用。

# 这里sift函数构建的是一个小根堆
def sift(li, low, high):
    i = low
    j = 2 * i + 1
    temp = li[low]
    while j <= high:
        if j + 1 <= high and li[j + 1] < li[j]:
            j += 1
        if li[j] < temp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = temp

def heap_sort_top_k(li, k):
    # 取前k个元素
    topk = li[0:k]
    n = len(li)
    # 对前k个元素先建立小根堆
    for i in range((k - 2) // 2, -1, -1):
        sift(topk, i, k - 1)
    # 把原数组剩余元素和堆顶最小元素比较， 把大的数替换堆顶元素
    for i in range(k, n):
        if li[i] > topk[0]:
            topk[0] = li[i]
            sift(topk, 0, k - 1)
    # 对topk数组排序
    for i in range(k - 1, -1, -1):
        topk[i], topk[0] = topk[0], topk[i]
        sift(topk, 0, i - 1)
    return topk