1. Top K 算法到底在解决什么问题榜单每十分钟刷新一次候选池里躺着上亿条记录真正要展示给用户的只有前 100 个。Top K 算法分析这个题目乍一听像是教科书里最不起眼的一章——谁还不会排个序呢但真把它放进工程里跑一遍就会发现坑几乎全在细节上K 取 10 和取 10 万是两套完全不同的打法数据能装进内存和装不进内存是两条完全不同的路要求精确和允许近似又是两套思路。这篇东西想干的事就是把这条链路上所有需要做判断的地方摊开讲清楚从该选哪个方案到代码怎么写再到上线之后会在哪里翻车。它的适用范围其实很宽。写业务代码的同学可能只是想在推荐列表里取个 Top 20做数据处理的同学可能是要对几百 G 的日志做词频统计取 Top 1000做后端的同学可能是要在一个滑动窗口里实时维护热搜榜。基础不同没关系下面会从最朴素的思路一路讲到分布式和近似算法每一层都给出为什么、代价是什么、什么时候该退回去用简单方案。Top K 这个问题最迷人的地方在于它没有唯一正确答案只有在当前约束下最不坏的那个答案。1.1 先把问题说人话从一堆数里挑出最大的 K 个剥掉所有业务外衣Top K 的内核简单到可以用一句话说完给定 n 个元素和一个整数 KK 远小于 n 是常态找出这 n 个元素中按某个指标排序最靠前的 K 个。这里的靠前可以是数值最大也可以是最小可以是单字段也可以是复合打分。业务里常见的形式有三种值得分清楚因为它们的解法并不一样。第一种是纯选择型从一堆已有记录里挑出得分最高的 K 条不做任何聚合。比如从一亿条商品记录里选出销量最高的 100 个 SKU。第二种是聚合型先按键分组求和或求次数再取分组后的 Top K。比如统计一亿条搜索日志里出现频次最高的 100 个查询词这时候Top K之前必须先做一次 group by本质上是 WordCount 加 Top K。第三种是流式型数据不是一次性给全的而是一条一条流过来你要持续维护一个当前最新的 Top K。热搜榜、实时成交榜都属于这一类。这三种形态的共同点是K 很小不同点在于数据能不能二次访问、需不需要维护状态。搞清楚自己属于哪一种比背下来十种算法都有用。我见过太多人拿着流式场景去套快速选择——快速选择要求数据可以随机访问和交换流式数据连完整保存都做不到套上去必然行不通。1.2 为什么排完序再截取是个陷阱新手最自然的想法是全部排一遍序取前 K 个不就完了这个方案在 K 和 n 都不大时完全没问题甚至是最优选择因为它简单、不易出错、还能顺便得到完整顺序。问题出在规模上。排序的信息量是 n log n而 Top K 需要的信息量只有 n。换句话说你为了让第 101 名也知道自己排第几付出了大量无谓的比较。更直接的代价是内存假设每条记录压缩后 32 字节一亿条就是 3.2 GB 的原始数据再加上排序过程中产生的索引数组和对象开销实际峰值往往要翻两三倍。一台 8G 内存的机器直接就 OOM 了。而如果只维护 100 个候选占用的内存是 3.2 KB 级别差了六个数量级。还有一个常被忽略的点是数据移动成本。现代 CPU 上比较两个整数只要一两个时钟周期但把元素从内存搬进缓存要几十上百个周期。全量排序意味着大规模的元素交换和随机访问缓存命中率极差而 Top K 的堆方案是顺序扫一遍数据绝大多数元素只需要和堆顶比一次就被丢弃几乎没有额外内存写入。同样是扫一亿条数据前者可能是几十秒后者可能不到一秒。这个差距不是算法复杂度表上的 log 因子能完全解释的它来自内存访问模式。注意这里说的排序是陷阱只针对 n 大 K 小的场景。如果 K 和 n 是一个数量级比如一亿条数据取前五千万那老老实实排序反而是对的任何花哨的技巧都省不下多少东西还容易写错。1.3 场景盘点Top K 藏在哪些角落把视野拉开一点会发现Top K 几乎是所有排行榜类需求的地基只是很多时候它藏在别的名字下面。内容社区的熱榜、电商的销量榜、音乐平台的热歌榜、招聘平台的活跃职位榜本质上都是聚合型加流式的组合。搜索引擎的召回阶段要从倒排链里取打分最高的几百个文档那是纯选择型。推荐系统的召回层要从百万候选里粗筛出几千个也属于这一类。数据库的ORDER BY ... LIMIT K更是把 Top K 做成了执行计划里的一个专门算子。再往底层走Top K 的思路还出现在很多不那么直观的地方。比如异常检测里取距离最远的 K 个样本图算法里取权重最大的 K 条边压缩算法里的 K 路归并甚至机器学习里的 K 近邻分类——找最近的 K 个邻居本质就是一次带距离函数的 Top K。理解了这一点你就会明白为什么面试官喜欢问这个题它小到可以在白板上写完又大到可以考察你对内存、并发、分布式的理解深度。不同场景对精确的要求差别也很大。账单排行榜、结算类榜单差一名都是事故必须精确。而内容推荐里的你可能感兴趣的前 20 个少一个多一个用户根本感知不到完全可以接受近似结果换取十倍的吞吐提升。这个判断得在动手写代码之前做出来因为它直接决定了你能不能上概率数据结构。1.4 五种解法一张表看清在往下拆之前先把全貌摆出来。下面这张表是我自己整理速查用的复杂度里的 n 是数据总量K 是目标数量m 是去重后的键数量或者值域宽度。方案时间开销额外空间数据能否二次访问典型适用区间全量排序O(n log n)O(n)需要K 与 n 同量级或本来就要全序小顶堆O(n log K)O(K)不需要一遍流式K 较小几十到几万流式场景快速选择平均 O(n)最坏 O(n²)O(1) 原地需要随机访问数据在内存、只要求无序的 Top K计数/桶O(n m)O(m)不需要值域窄比如评分 0-100分片归并O(n log K / P)O(K·P)不需要单机放不下或多核并行概率结构O(n) 单次误差可控O(m) 固定不需要超大规模流式允许近似这张表最值得盯的是额外空间那一列。很多人选型时只看时间复杂度结果在内存这一关卡死。小顶堆和分片归并之所以在工程里出现频率最高核心原因就是它们把空间压到了与 n 无关。记住一句话Top K 的战场从来不在时间上而在空间和访问模式上。2. 五种主流解法的原理拆解与代价分析2.1 全局排序最省心的基线方案全量排序的价值在于它是唯一的零思考方案。调一个库函数结果稳定可靠还能顺带拿到完整排名、分页、并列处理这些附加能力。在数据量不超过千万、K 又不太小的场景里我个人的建议就是直接用排序不要为了炫技去手写堆。理由很实际排序库经过几十年优化常数因子极低而手写代码引入的 bug 风险和调试成本远高于那点理论收益。但它有个硬约束——必须能把全部数据放进内存。一旦数据要外排到磁盘情况就完全变了外部排序虽然还是 O(n log n)但每次归并都要读写磁盘吞吐会掉一到两个数量级。这时候正确的做法不是优化排序而是换方案先用堆在流式扫描中拿到候选集把 n 降成 K后面的操作就都在小数据上做了。还有一个隐藏成本容易被忽略排序会改变元素的相对顺序。如果原始数据有业务上的先后含义比如按时间到达的日志排序后这个信息就丢了。要在同分情况下保持原有先后就得用稳定排序而稳定排序通常要额外一份索引空间。这个细节在做同分按提交时间先后来的榜单时会咬人。2.2 小顶堆K 个元素组成的守门员小顶堆是 Top K 里最经典也最实用的方案思路可以用一句话概括维护一个只有 K 个座位的候场室座位满了之后新来的人只有比候场室里最差的那个强才有资格把他挤走。求最大的 K 个用小顶堆求最小的 K 个用大顶堆。这个方向反直觉但逻辑很直白——堆顶必须是当前第 K 名它就是这个门槛方便 O(1) 时间判断新人有没有资格。具体流程分两段。前 K 个元素直接入堆然后自底向上建堆这一步是 O(K) 而不是 O(K log K)很多人写成了逐个 push白白多花一个 log。第 K1 个元素开始每个元素先和堆顶比一次比不过就直接丢弃这次比较是 O(1)比得过就替换堆顶并向下调整代价是 O(log K)。所以总开销是 O(n log K)但因为绝大多数元素在第一关就被刷掉了实际耗时非常接近一次线性扫描。这里有个很实用的估算公式在数据随机分布的情况下堆被替换的期望次数大约是K · ln(n/K)。代入具体数字感受一下n 1 亿K 100那么 100 × ln(10⁶) ≈ 100 × 13.8 ≈ 1380 次。也就是说扫一亿条数据真正触发堆调整的只有一千多次其余全是廉价的比较。这个数字解释了为什么堆方案在实际跑分里能碾压排序——省掉的不是复杂度是实打实的内存写操作。写堆最容易翻车的地方是方向搞反。求 Top 100 大结果建了个大顶堆那堆顶就是当前最大值新元素永远比不过它最后堆里留下的是前 100 个元素里最小的那批——完全反了。这个错误极其常见而且在小数据量测试时不一定暴露因为如果数据是递增的两种写法结果看起来都对。测试用例里一定要放一组乱序数据。提示JDK 的PriorityQueue默认就是小顶堆Python 的heapq也是小顶堆。所以求最大的 K 个这两个语言里正好可以直接用默认行为不用写比较器。反过来求最小的 K 个才需要自定义比较器。这个巧合让不少人记住了错误结论。2.3 快速选择把平均复杂度压到 O(n)快速选择的思路借自快速排序既然我只需要知道前 K 个是谁那就不必把左右两边都排好。选一个基准值把数组划分成大于它和小于它两段如果左边那段的长度正好是 K活干完了如果左边比 K 多说明答案全在左边右边整段可以扔掉如果左边不够 K那就把左边全收下再去右边找剩下的部分。每次只需要递归处理一侧期望复杂度从 O(n log n) 降到 O(n)。这个 O(n) 的常数大概是 3.4n 次比较随机基准下的平均值比堆的 n log K 在 K 较大时有明显优势。举个例子n 1000 万K 10 万堆要做大约 1000 万 × 17 ≈ 1.7 亿次量级的操作快速选择大概 3400 万次比较差五倍左右。所以经验法则是K 小于 1000 用堆K 超过 n 的 1% 可以考虑快速选择当然具体分界线要看实测。它的问题也很清楚。第一必须要能随机访问和交换元素链表、流式数据都用不了。第二最坏情况会退化到 O(n²)虽然随机化基准能把这个概率压到极低但在对抗性输入或者大量重复值面前依然会出问题。第三它只保证前 K 个元素都在不保证它们有序要输出有序榜单还得再对 K 个元素排一次那部分开销是 O(K log K)通常可以忽略。大量重复值是快速选择的头号杀手。假设一亿条数据里只有三种取值朴素的单路划分会把数组切成极度不平衡的两段递归深度直接飙到 n。解决办法是改成三路划分把数组分成大于基准等于基准小于基准三段等于基准的那段整体跳过。这一改动让算法在重复值场景下依然稳健代码只多几行非常值得。2.4 计数与桶值域有限时的降维打击如果排序的键不是任意数值而是取值范围很窄的整数——比如用户评分 0 到 100、订单状态只有十几种、年龄 0 到 120——那前面所有方案都是在浪费。直接开一个长度为值域宽度的计数数组扫一遍数据把每个值出现次数累加然后从高到低累加计数直到凑够 K 个。整个过程 O(n m)m 是值域宽度而且完全不需要比较。这个方案的威力在于 m 通常极小。评分场景 m 101一亿条数据扫一遍只要几百毫秒内存占用 101 个整数。任何基于比较的方案都不可能比它更快因为理论上基于比较的排序下界就是 n log n。这就是所谓的降维打击——换一种数据表示问题的难度直接塌掉。桶排序是它的推广版适用于值域宽但分布集中的情况。把值域切成一万个区间先统计每个区间的元素数量从高到低累加找到第 K 名落在哪个桶里然后只对这个桶做精确处理。这一步把 n 缩小到了一个桶的规模通常只有几千个元素后面怎么排都无所谓了。推荐系统的粗排打分经常用这招因为分数虽然理论上是浮点数但落在高分段的数据其实很稀疏。要注意的是浮点数做桶排序要小心边界。分数的精度、NaN 值、正负零都会带来意外而且桶边界的选择会直接影响效果——分桶太粗最后一个桶里元素太多退化成小规模排序分桶太细桶数组本身的内存又上去了。我自己的经验是按目标 K 的十倍左右来定桶数比如取 Top 1000 就开一万个桶落点比较均匀。2.5 分治归并数据装不进一台机器时前面所有方案都默认数据能进内存。一旦数据量到几十 G 甚至 TB 级就必须换思路把大问题切成小问题每个小问题独立求出局部 Top K再把这些局部结果归并成全局 Top K。这个切分可以是多线程分块同一台机器内也可以是分布式分片多台机器算法骨架完全一样。关键结论是每个分片只需要保留自己的前 K 名不需要更多。这个结论不是近似是严格的。证明很简单——假设全局第 K 名是 xx 落在分片 A 里那么分片 A 中比 x 大的元素最多只有 K-1 个否则全局排名就超过 K 了所以 x 在分片 A 内的排名一定在前 K 之内。反过来如果某个元素在自己分片内排到了 K 名之外那它前面已经有 K 个更大的元素它在全局必然进不了前 K。所以每片取 K 个一个都不会漏。这个性质让最后的归并变得极其廉价P 个分片各出 K 个总共 P×K 个元素再对这堆数据做一次 Top K 就完事了。就算 P 1000、K 1000归并阶段也只有一百万条数据单机轻松搞定。整体开销从处理 n变成了处理 n/P 再处理 P·K几乎是线性加速。实现上要注意分片策略。哈希分片和范围分片效果不同哈希分片能让数据均匀分布但每个分片都可能包含高价值元素范围分片比如按用户 ID 区间可能造成热点某些分片数据量是别人的十倍拖长整体时间。用哈希分片加动态负载均衡更稳。另外归并阶段别用递归写成多轮一轮就够了多轮归并没有收益反而多一次传输。2.6 近似结构当差不多就够用时如果场景允许误差还有一条更激进的路——用固定大小的概率数据结构在单遍扫描中估计出近似的 Top K。这类结构的共同特点是空间与 n 完全无关只和精度要求挂钩特别适合每秒几百万条的实时流。最常被提起的是 Misra-Gries 和 Space-Saving 这两种重元素算法。它们的思路都是维护 m 个计数器槽位新元素来的时候如果已经有槽位就加一如果没有槽位且还有空位就占一个如果槽位满了就把所有计数器统一减一Misra-Gries或者替换掉计数最小的那个槽并把它的计数加到这个新元素上Space-Saving。前者能保证找出所有出现次数超过 n/m 的元素后者能在同样空间下给出更准确的估计值。误差界是可以量化的用 m 个槽位时估计值和真实值的偏差不超过 n/m。取 m 1000n 1 亿偏差上限就是 10 万次。对于热搜词这种动辄百万量级的场景这个误差完全可以接受——第 3 名和第 4 名差个几万次用户看不出来。但如果你的场景是结算榜单那就别碰这类结构一分钱都不能错。注意概率结构的输出是不稳定的两次运行可能给出略有差异的榜单。如果你要做榜单不允许跳变的产品体验还得在外面套一层平滑或者滞后处理否则用户会看到第 10 名和第 11 名来回横跳。3. 手把手落地从单机实现到分布式链路3.1 需求量化K 值、数据量、时效性三要素动手之前先把三个数确定下来这三个数基本能锁定方案。第一个是数据总量 n 和单条大小用它算内存n × 单条字节数如果超过可用内存的一半就得考虑流式或分片。第二个是目标 K用它和 n 的比值选算法K/n 小于千分之一用堆大于百分之一用快速选择中间看实测。第三个是时效性要求全量批处理、准实时分钟级、实时秒级对应的架构完全不同。举个具体例子走一遍。假设场景是一亿条商品记录要取销量最高的 100 个每 10 分钟刷新一次。n 10⁸K 100K/n 10⁻⁶单条记录假设 id 8 字节加销量 8 字节共 16 字节那么堆方案的内存是 100 × 16 1.6 KB几乎是零。全量排序的内存是 10⁸ × 16 1.6 GB还没算排序的开销。结论很清楚堆方案单机扫描十分钟一次完全没压力。再换一个。假设是一亿条日志里取出现次数最多的 1 万个查询词。这是聚合型先要 group by。如果内存放得下一亿条的去重键值对通常去重后只有几百万那就用哈希表统计然后对哈希表做一次 Top KK 10⁴ 属于中等规模可以用堆也可以用快速选择。如果去重后键还是太多就得先做一轮哈希分片每片统计后取本地 Top K 再归并。这一步最容易被跳过但它的价值最高。我见过太多次上来就写分布式最后发现单机一个堆循环就解决了白白多了一堆运维负担。先算出那个数字再决定要不要复杂化。3.2 小顶堆版实现与三个容易踩的细节下面这段是求最大的 K 个元素的最小可用版本Python 写的逻辑清晰但不完全健壮后面几个细节就是专门讲它为什么不健壮。import heapq def topk_max(records, k): if k 0: return [] heap [] for item in records: score item[score] if len(heap) k: heapq.heappush(heap, (score, item)) elif score heap[0][0]: heapq.heapreplace(heap, (score, item)) return [pair[1] for pair in sorted(heap, keylambda p: p[0], reverseTrue)]第一个细节元组比较的隐式陷阱。堆里存的是(score, item)当两条记录的 score 完全相等时Python 会去比较第二个元素 item。如果 item 是字典比较直接抛TypeError如果 item 是自定义对象且没实现比较方法同样报错。这个 bug 只在出现并列分数时触发测试数据里没有并列就发现不了上线后遇到真实数据立刻炸。修法是插入一个单调递增的序号(score, seq, item)让比较在 score 和 seq 就分出胜负永远走不到 item。第二个细节初始容量。Java 里new PriorityQueue(0)会直接抛IllegalArgumentException因为初始容量必须大于等于 1。如果你按 K 来初始化而 K 可能为 0比如配置读错、前端传了 0程序当场崩溃。老老实实写Math.max(1, k)或者干脆不传容量用默认值反正 K 小的时候扩容几次无所谓。第三个细节输出顺序。堆内部的顺序是堆序而不是有序直接遍历堆输出得到的榜单是乱的。必须额外排一次成本 O(K log K)K 小时可以忽略。如果下游要求榜单严格有序而你又想省这一次排序也可以在堆满之后额外维护一个有序结构但通常不值得。还有一个不那么明显但影响很大的点如果 K 大于等于 n上面的代码会走完整循环等价于全量入堆再排序退化成排序没有错误但也没有收益。判断一下提前走全排序分支语义更清晰。3.3 快速选择版实现迭代写法与重复值处理快速选择的递归写法很漂亮但有栈溢出风险工程里我推荐迭代版本用一个 while 循环维护当前搜索区间。下面这版用了三路划分专门对付重复值。def topk_quickselect(arr, k): if k 0: return [] if k len(arr): return sorted(arr, reverseTrue) left, right 0, len(arr) - 1 target k - 1 while left right: pivot arr[(left right) // 2] lt, i, gt left, left, right while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[gt], arr[i] arr[i], arr[gt] gt - 1 else: i 1 if target lt: right lt - 1 elif target gt: left gt 1 else: break return sorted(arr[:k], reverseTrue)lt是大于基准区的右边界gt是小于基准区的左边界中间那段是等于基准的整体跳过。这样即使数组里只有两种取值一次划分也能把问题规模砍半不会退化。基准的选择也有讲究。取中间位置的元素在随机数据上表现不错但遇到已经有序的输入比如数据本身按时间递增中间元素仍然能把数组均匀切分所以比取首元素安全。如果数据可能有对抗性构造可以加一步随机化pivot arr[random.randint(left, right)]。随机化的代价是一次伪随机调用换来的是期望复杂度的保证通常值得。提示如果对最坏情况有硬性要求还有 BFPRT 算法中位数的中位数能保证最坏 O(n)但常数大约是快速选择的三到五倍。实际工程里几乎没人用它随机化快速选择的期望性能已经足够好退化概率可以忽略。3.4 并行化分块加本地堆加归并单机多核的场景下最直接的加速方式是把数据切成 P 块每个线程拿一块跑自己的小顶堆最后把 P 个堆的结果合并。这里要注意两点。第一块不要切得太碎。每个线程处理的数据量最好在百万级以上否则线程调度和结果合并的开销会吃掉并行收益。P 取 CPU 核数或者核数的两倍就够了再多没意义。第二合并阶段可以直接复用同一个堆。把所有线程的本地结果依次喂进一个全局堆因为每个本地结果只有 K 个元素总输入是 P×K合并成本是 O(P·K·log K)通常几毫秒就完事。不需要写专门的归并逻辑直接复用现有的 topk 函数最省事。实测下来加速比大概是 P 的 0.7 到 0.9 次方8 核能拿到 5 到 6 倍。达不到线性是因为扫描内存本身受内存带宽限制多线程抢总线。如果你的瓶颈是 CPU 密集的打分计算而不是单纯比较加速比会更接近线性。3.5 分布式归并的正确性说明前面提过每片只留 K 个的结论这里把完整流程串一遍因为这是分布式 Top K 的核心写错一步就全错。第一步分片。按某个键的哈希值把数据分发到 P 个处理单元。哈希的好处是数据均匀不会出现某个分片特别大的长尾。第二步本地聚合。每个分片独立完成统计如果需要去重计数并取本地 Top K。注意这里必须是 Top K 而不是 Top k小 kK 就是全局目标值不能省。第三步汇总。把 P 份本地 Top K 收集到一个节点总共 P×K 条数据再跑一次 Top K 得到结果。这一步的数据量已经很小单机毫秒级。第四步排序输出。最后再对 K 个元素排一次序给出有序榜单。整个链路里唯一可能出错的地方是第二步的 K 值。有人为了省内存让每个分片只留 K/2 个觉得这样就够了——错得离谱。全局第 K 名可能在某个分片里正好排第 K你只留 K/2 就把它扔了结果必然错。必须严格留 K 个一视同仁。3.6 流式与滑动窗口让榜单会过期流式场景下数据是一条条来的而且业务上通常只关心最近一段时间的 Top K。最简单的实现是滑动窗口加小顶堆但堆不支持删除任意元素过期数据会一直留在堆里。常见的解法有三种。第一种是双堆加延迟删除。维护一个窗口内的元素堆和一个待删除集合取堆顶时检查是否在待删除集合里是就弹出。实现简单但待删除集合会无限增长需要定期清理。第二种是分桶时间轮。把时间切成固定长度的桶每个桶内维护一份局部 Top K查询时把最近若干个桶的结果合并。老桶直接整桶丢弃内存可以精确控制。缺点是桶边界上的数据会被截断比如一个元素横跨两个桶可能出现重复或遗漏需要额外处理。第三种是计数衰减。不删数据而是定期给所有计数乘以一个衰减系数比如每过一分钟乘 0.9。这样老数据的影响力自然下降不需要显式删除。热度分公式通常是score base × exp(-λ × age)λ 控制衰减速度age 是距今时长。这招在内容推荐里很常见因为它天然平滑不会出现榜单剧烈跳变。我个人的偏好是分桶方案因为它的内存上限是确定的不用怕流量突增把堆撑爆。衰减方案虽然平滑但每次衰减都要遍历所有候选在候选集很大时成本不低。4. 常见问题与排查技巧实录4.1 踩坑速查表下面这张表是我这些年攒下来的问题清单基本都是自己踩过或者帮别人排查过的。现象最可能的原因排查方向结果完全反了取到了最小的 K 个堆的方向搞反求最大 K 个必须用小顶堆检查比较符号出现并列分数时抛异常元组/对象比较失败插入单调序号避免比较业务对象数据量大时结果缺失部分元素分片只留了 K/2 或更少每个分片必须严格保留 K 个榜单顺序混乱直接遍历堆输出堆序不是有序需额外排序重复值多时耗时暴涨快速选择未做三路划分检查划分逻辑加等值区内存持续上涨滑动窗口未清理过期数据检查删除逻辑用分桶限内存多线程结果偶尔不一致共享堆未加锁用本地堆加归并避免共享状态浮点分数排序异常出现 NaN 或精度误差过滤 NaN比较用定点数或加误差阈值4.2 边界条件清单写 Top K 最容易出事的地方不是主逻辑而是边界。每次提测前我都会对着这张清单过一遍K 等于 0、K 为负数、K 等于 1、K 等于 n、K 大于 n、数组为空、数组只有一个元素、所有元素相同、所有元素严格递增、所有元素严格递减、存在大量重复值、存在 null 或缺失值、分数出现 NaN 或无穷大、并发写入的同时在读取。其中最有迷惑性的是K 大于 n。逻辑上应该返回全部元素但很多实现会因为堆始终没满而走完整个流程最后返回的顺序还是乱的。另外K 等于 1也是高频 bug 点因为此时堆退化成单元素任何依赖堆结构的假设都不成立。4.3 被追问时的回答思路这类问题在技术评审里经常被追问为什么不换个方案。我的回答框架是先给约束再给选择数据量多大、能不能进内存、K 多大、允不允许近似、要不要有序。这五个问题一答方案基本就唯一了。比如一亿条数据、K 是 100、必须精确、不需要全序那答案就是小顶堆没有第二个选项谁来说都一样。另一个常见的追问是最坏情况怎么办。快速选择的最坏是 O(n²)堆的最坏也是 O(n log K) 但常数稳定所以在有硬性延迟要求比如必须 100 毫秒内返回的接口里我会选堆而不是快速选择尽管堆的平均性能更差一点。工程选型看的是尾部延迟不是平均值这一点想清楚了很多争论自然就没了。5. 选型决策与延展方向5.1 一条可以照着走的决策路径把前面的内容压缩成一条可执行的判断链遇到新需求时从上往下走第一个命中的就是答案。先看数据能不能全部放进内存。放不下走分片归并或者外部排序加堆。放得下再看 K 和数据量的比值。K 和 n 同量级直接全量排序别折腾。K 小于 n 的千分之一用小顶堆一遍扫完。K 在千分之一到百分之一之间两者都试试看实测。K 大于百分之一用快速选择。如果值域很窄不管 K 多大优先用计数或桶排序。再看是否需要流式或者近似。如果是持续到达的数据堆加滑动窗口是标配。如果数据量到了单机内存的几十倍而且允许误差上 Space-Saving 这类结构空间可以压到常数级别。最后看是否需要有序输出、是否需要稳定排序、是否有并列名次的业务规则这些会决定最后那一步排序怎么写。5.2 还能往哪儿扩展这个题目的延展方向比它本身有意思得多。一个方向是带约束的 Top K比如每个品类最多取 3 个的多样性约束、不能有重复作者的打散约束。这时候单纯的堆就不够了得在插入时做一次可行性检查算法复杂度上去了但业务价值也上去了。另一个方向是动态更新数据不是重新计算而是增量变化。比如某个商品的销量实时加一榜单怎么更新朴素的做法定时全量重算简单但浪费。进阶做法是维护一个有序结构比如跳表或平衡树每次更新 O(log n)代价是内存和实现复杂度。这里要权衡的是更新频率和重算成本如果十分钟才更新一次全量重算完全够用。最后一个方向是分布式下的时钟与一致性。多个节点各自维护本地 Top K合并时如果数据有时间戳就得处理乱序到达和重复上报。这时候问题从算法变成了工程需要考虑幂等、去重、水位线这些东西。做到这一步Top K 已经不是一个算法题而是一个完整的流处理系统设计了。我个人在实际项目里体会最深的一点是绝大多数时候最简单的方案就够了。真正需要快速选择、需要概率结构、需要分布式归并的场景比例远低于想象。先把单机堆写对、测试覆盖好边界、把监控埋上比上来就搞一套分布式架构要值钱得多。等到监控告诉你单机确实扛不住了再动手升级那时候你也有真实数据支撑决策了。最后分享一个调试小技巧写 Top K 的时候顺手加一个开关把全排序后取前 K的结果作为对照跑一遍两边做 diff。数据量小的时候这个对照几乎不花时间但能抓住 90% 的逻辑错误。等数据量大了再关掉开关用采样数据做对照。这个习惯帮我省下过好几次线上事故。
