外观
09 - Top K 问题:排行榜为什么不需要每次全量排序
前置阅读:05 - 栈与队列的解题模型、08 - 排序算法怎么选。
分布式场景可结合负载均衡算法与慢节点理解分片与倾斜问题。
摘要
从百万条指标记录中找数值最高的 100 条,不必确定其余记录的完整顺序。Top K 就是按指定规则选出排在前 K 位的元素。本文先解释堆如何快速找到候选中的最小值,再用固定大小的小顶堆保留最大的 K 个数,最后比较全量排序、Quickselect 和分布式合并。
先明确需要哪种结果:第 K 大的值、最大的 K 个值(不要求有序)、按降序排列的 Top K,还是同分时也有确定次序的对象榜单。本文的整数示例按元素出现次数计数,不去重;例如两个相同数值可以各占一个名额。
1. 堆是什么
本文讨论的 Heap(堆)是数据结构,与 JVM 分配对象的堆内存含义不同。这里使用二叉堆:它的形状是一棵完全二叉树,即除了最后一层,其他层都填满,最后一层从左向右连续填入。这样的节点可以按层存进数组,不需要为每个节点保存左右子节点的指针。
小顶堆要求每个父节点的值都不大于其子节点。沿任何路径向下,值都不会小于根,因此根节点是整个堆的最小值。这个约束只规定父子关系,不保证兄弟节点或数组整体有序。大顶堆则反过来,父节点不小于子节点,根是最大值。
数组下标从 0 开始时,对下标 i:
text
parent = (i - 1) / 2
left = 2 * i + 1
right = 2 * i + 2parent 的除法取整数部分,且只用于 i > 0;根没有父节点。子节点下标只有小于当前堆大小时才存在。
插入时,先把新值放在数组末尾,保持树的形状。如果它比父节点小,就交换并继续向上比较,这叫上浮。删除根时,把末尾元素移到根并缩小堆;若它大于子节点,就与较小的子节点交换,继续向下比较,这叫下沉。选择较小子节点,才能同时满足两个子节点与父节点的大小约束。
堆有 n 个元素时,树高为 O(log n),上浮和下沉只沿一条路径进行,因此插入、删除根的调整成本为 O(log n);查看根不需要调整。
2. 固定大小小顶堆求最大 K 个
令 n 为输入元素数,候选堆最多容纳 K 个数。逐个读取输入:堆未满时直接加入;堆满后,只让大于堆顶的新值替换堆顶,其余值跳过。堆顶就是当前进入 Top K 的门槛。
下面是需要放入 Java 类中的局部方法,要求 values 非 null,且 0 <= k <= values.length;非法 K 会抛出异常。PriorityQueue 是优先队列,按优先顺序取出元素;这里的整数默认按自然升序比较,用它维护小顶堆。offer() 加入元素,peek() 查看堆顶,poll() 取出并删除堆顶。
java
import java.util.PriorityQueue;
static int[] topK(int[] values, int k) {
if (k < 0 || k > values.length) {
throw new IllegalArgumentException("invalid k");
}
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int value : values) {
if (heap.size() < k) {
heap.offer(value);
} else if (k > 0 && value > heap.peek()) {
heap.poll();
heap.offer(value);
}
}
return heap.stream().mapToInt(Integer::intValue).toArray();
}每轮结束后,堆中保留已读元素中最大的至多 K 个数。这个每轮都成立的约束称为不变量,下一节会解释它为什么成立。k=0 时,代码不会访问空堆的堆顶,最终返回空数组;k=n 时保留全部元素。
当 k >= 2,扫描 n 个元素,每次堆调整最多经过 O(log k) 层,总时间为 O(n log k),堆及返回数组占用 O(k) 空间。k=1 时只需维护一个最大值,扫描成本为 O(n);这段代码在 k=0 时也仍会扫描输入。以上按整数比较成本为常数分析。
heap.stream() 遍历优先队列,不保证按大小排序,因此返回数组未排序。若需要降序结果,还需对这 K 个值排序,或像第 5 节一样反复取出堆顶后倒序填入数组,额外时间为 O(k log k)。
3. 为什么最大 K 用小顶堆
假设堆已经保留已读数据中最大的 K 个数,堆顶为 m。新值 v <= m 时,已有 K 个候选都不小于 v,跳过它仍能保留最大的 K 个值;v > m 时,淘汰 m、加入 v,候选集合仍是新的 Top K。这就解释了上一节的不变量。
需要快速找到的是候选中最该淘汰的最小值,所以求最大 K 个数使用小顶堆。大顶堆只能直接给出候选中的最大值,无法用堆顶判断谁该被淘汰。求最小 K 个数时,则使用大顶堆维护淘汰边界。
整数值相等时,保留哪一次出现不影响本例的数值结果。若候选是有身份的记录,需要先定义同分时按哪个字段比较,再用同一规则维护堆;堆不会自动保留同分记录的原始顺序。
4. 方案比较
| 方案 | 时间 | 空间/特点 |
|---|---|---|
| 全量排序 | O(n log n) | 简单,可得到完整顺序 |
| 大小 K 的堆 | O(n log k) | 适合流式数据 |
| Quickselect | 平均 O(n) | 原地选择,最坏情况需关注 |
**Quickselect(快速选择)**借用快速排序的分区思想:选择基准值(pivot),把不大于它的值放到一侧,较大值放到另一侧,再只处理包含目标名次的一侧。它不需要把两侧都排好,所以适合一次性数组中求第 K 大的值。若还需要排序后的 K 个结果,选择后仍要排序这些候选。
表中的堆成本对应候选选择阶段,k >= 2;排序后的输出还有上一节说明的额外工作。Quickselect 的平均线性时间依赖输入分布或基准选择方式,朴素实现最坏可达 O(n²)。原地选择指在输入数组内调整元素,第 5 节为了保留输入先复制数组,因此那段实现额外占用 O(n) 空间。
若数据不断到来,也就是流式数据,堆只需保存当前候选,无需保存全部历史输入。前提是目标为已到达、仅追加数据的 Top K;本文的函数接收数组,展示的是候选维护逻辑,并未实现流式读取接口。若需要完整顺序,或 K 接近 n,应结合输出要求和实际数据比较全量排序与堆方案,不能只凭复杂度判断实际耗时。
5. 完整可运行示例:Top K 与 Quickselect
下面的类对应文件名 TopKDemo.java,包含 main 入口。数组参数均要求非 null:topK 接受 0 <= k <= a.length,返回降序排列的 K 个值;kthLargest 接受 1 <= k <= input.length,只返回第 K 大的值。两者都不修改调用方的输入数组。
java
import java.util.*;
/**
* 可运行示例:Top K 问题:排行榜为什么不需要每次全量排序。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class TopKDemo {
static int[] topK(int[] a, int k) {
if (k < 0 || k > a.length) throw new IllegalArgumentException();
PriorityQueue<Integer> q = new PriorityQueue<>();
for (int v : a) {
// 前 k 个元素先填满候选集合。
if (q.size() < k) q.offer(v);
else if (k > 0 && v > q.peek()) {
// 堆顶是当前 Top K 中最小值,也是进入榜单的门槛。
q.poll();
q.offer(v);
}
}
int[] out = new int[k];
for (int i = k - 1; i >= 0; i--) out[i] = q.poll();
return out;
}
static int kthLargest(int[] input, int k) {
if (k < 1 || k > input.length) throw new IllegalArgumentException(
"invalid k"
);
int[] a = Arrays.copyOf(input, input.length);
// 第 k 大等价于升序排列后下标 length-k 的元素。
int target = a.length - k,
l = 0,
r = a.length - 1;
while (l <= r) {
int p = partition(a, l, r);
if (p == target) return a[p];
if (p < target) l = p + 1;
else r = p - 1;
}
throw new AssertionError();
}
static int partition(int[] a, int l, int r) {
int p = a[r],
s = l;
// [l, s) 始终保存不大于 pivot 的元素。
for (int i = l; i < r; i++) if (a[i] <= p) {
int t = a[i];
a[i] = a[s];
a[s++] = t;
}
int t = a[s];
a[s] = a[r];
a[r] = t;
return s;
}
// 运行入口:演示普通输入;边界情况需另行测试。
public static void main(String[] args) {
int[] a = { 3, 2, 1, 5, 6, 4 };
System.out.println(Arrays.toString(topK(a, 3)));
System.out.println(kthLargest(a, 2));
}
}手工推演固定大小堆
求 [3,2,1,5,6,4] 的最大 3 个数:先放入 3、2、1,堆顶门槛为 1;读到 5 时淘汰 1,读到 6 时淘汰 2,读到 4 时淘汰 3,最终保留 4、5、6。
完整示例的 topK 反复弹出最小值,依次填到数组末尾,所以预期返回 [6, 5, 4]。kthLargest(a, 2) 的预期结果为 5。这是手工推导的两行预期输出,不是实际运行记录。
kthLargest 将第 K 大转换成升序下标 length-k。partition 在闭区间 [l, r] 内使用末尾值作为基准;返回下标 p 后,左侧值都不大于 a[p],右侧值都大于它。若 p 小于目标下标,只需继续右侧;若大于目标,只需继续左侧;相等时即可返回,不必让其他位置有序。
示例固定选择末尾元素作为基准,只适合教学。对升序或全相等数组,这种分区每次可能只排除一个元素,累计扫描量呈平方级增长。面对调用方可控制的输入或稳定延迟要求,需要评估基准选择策略:随机基准是随机选元素,三数取中是取三个候选值的中间值;这两种策略不能提供最坏线性时间保证。若要求该保证,应评估具有最坏线性保证但常数更高的选择算法;具体方案仍要通过目标数据分布验证。
6. 分布式 Top K
分片是把数据划分成多个部分,由不同节点分别处理。若有 shardCount 个分片,每个分片先返回本地 Top K,再从至多 shardCount × K 个候选中求全局 Top K,能够避免汇总全部数据。
这个结论成立的前提是各分片和合并端排序规则一致,且目标是可按同一全序比较的全局 Top K。全序在这里指任意两条记录都有一致、确定的先后关系,同分时也按约定字段区分。某条记录若不在本地 Top K 中,本地就已有至少 K 条记录排在它前面;这些记录在全局仍排在它前面,因此它不会进入全局 Top K。
若存在去重、时间窗口、迟到数据或分片只返回不足 K 个候选,合并协议必须额外定义。时间窗口限定参与排名的数据范围,迟到数据则是超过预期时间才到达的记录。例如多个分片返回同一对象,合并后去重可能导致候选不足;某分片本来少于 K 条,返回全部记录是正常情况,但主动截断或漏报候选可能丢失答案。若目标是先跨分片累加对象分数、再排名,也不能直接套用上述记录比较模型。
数据倾斜指各分片负载不均。在前述条件满足时,它不会破坏算法正确性,但可能让单个分片承担大部分计算和存储压力。
7. 验证与排障
先核对输出要求,再做正确性测试。以下是测试与排障建议:
- 用完整排序结果作为小规模基线。无序 Top K 比较元素的多重集合,即每个值及其出现次数;降序 Top K 还要比较顺序。第 K 大则与排序后对应位置的值比较。
- 覆盖空数组、
k=0、k=1、k=n、重复值、负数和非法 K。注意k=0对topK合法,对kthLargest非法;还需用有序、逆序和全相等输入检查 Quickselect 的退化。 - 对对象榜单,使用相同分数的记录验证次级排序键;确认所有分片与合并端使用同一比较规则。
- 监控堆大小、处理元素数、比较次数和分片候选数。延迟异常时区分输入规模增大、比较器成本增加、对象分配和分片倾斜,避免把所有耗时都归因于堆调整。
8. 容易踩的坑
- K 为 0 时仍按堆顶做数值比较,访问空堆。
- 把
PriorityQueue的遍历顺序当作排序结果,混淆第 2 节无序返回与第 5 节降序返回。 - 比较器方向选反,堆顶不能代表应淘汰的候选。
- 指标相等时没有定义次级排序键,却期望对象榜单顺序固定。
- 分布式场景满足局部候选合并条件时,仍汇总全部数据,增加传输和集中处理成本。
9. 工程延伸
排行榜还要处理并发更新、时间窗口、去重和相同分数排序。本文的堆算法只处理候选选择,不负责持久化一致性,即数据保存与并发修改能否符合约定的结果。
当记录过期或分数降低,曾被丢弃的候选可能重新进入榜单,仅保留 K 个元素就不足以恢复答案,需要额外的数据与更新机制。Redis Sorted Set(有序集合)等系统提供不同的工程实现,应结合数据量和更新模型选择;这里未核验它的具体实现或版本行为,也不据此给出性能结论。
10. 总结
Top K 的关键是只维护仍可能进入答案的 K 个候选,而不是为无关元素支付完整排序成本。
- 最大 K 通常使用小顶堆维护淘汰边界。
- 堆适合流式数据,Quickselect 适合一次性数组选择。
- 排行榜的相同分数、窗口和分布式合并仍需额外规则。
下一篇:区间问题统一解法。堆在贪心构造中的应用见贪心算法与正确性证明。