目录
什么是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