Python heapq:用固定容量保留数据流里最大的 K 个值

举报
yd_254857454 发表于 2026/11/17 10:18:58 2026/11/17
【摘要】 假设程序持续收到请求耗时,只想保留最大的三个值。不必存下所有记录,也不必每来一条就重新排序:只要知道当前候选里谁最小,就知道新值能不能进榜。 最小堆记录的是门槛当前候选为 10、12、15,门槛就是 10。新值 3 应被拒绝;新值 14 则淘汰 10。最小堆的 heap[0] 是最小值,但堆本身并不是排好序的列表。heappushpop 等价于先把新值纳入比较范围,再淘汰最小值。heapre...

假设程序持续收到请求耗时,只想保留最大的三个值。不必存下所有记录,也不必每来一条就重新排序:只要知道当前候选里谁最小,就知道新值能不能进榜。

最小堆记录的是门槛

当前候选为 10、12、15,门槛就是 10。新值 3 应被拒绝;新值 14 则淘汰 10。最小堆的 heap[0] 是最小值,但堆本身并不是排好序的列表。

heappushpop 等价于先把新值纳入比较范围,再淘汰最小值。heapreplace 则一定移除旧堆顶,再加入新值。无条件对初始堆执行 heapreplace(heap, 3) 会丢掉应该保留的 10。若用后者,需要先检查 heap[0] < value。

from heapq import heappush, heappushpop, heapreplace

heap = [10, 12, 15]
assert (heappushpop(heap, 3), sorted(heap)) == (3, [10, 12, 15])
assert (heappushpop(heap, 14), sorted(heap)) == (10, [12, 14, 15])

heap = [10, 12, 15]
assert (heapreplace(heap, 3), sorted(heap)) == (10, [3, 12, 15])

def top_k(values, k):
    if k <= 0:
        return []
    heap = []
    for value in values:
        if len(heap) < k:
            heappush(heap, value)
        else:
            heappushpop(heap, value)
    return sorted(heap, reverse=True)

assert top_k(iter([10, 12, 15, 3, 14]), 3) == [15, 14, 12]
assert top_k(iter([7, 7, 4, 7]), 2) == [7, 7]
assert top_k(iter([2, 1]), 5) == [2, 1]
assert top_k(iter([1]), 0) == []
assert top_k(iter([]), 3) == []

堆没满时直接加入,堆满后才筛选,输入不足 K 条时就会保留全部。重复值按出现次数保留,不自动去重。候选只占 O(min(N, K)) 空间;每次堆更新最多 O(log K)(K ≥ 2),最后才对候选排序。一次性查询可以直接用 heapq.nlargest,持续维护时再考虑自己持有堆。上述断言已在 Python 中运行通过。

参考:Python 标准库文档 heapq 模块。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。