擂台题目是从一百万个数里找最小的一千个。完整排序需要让所有元素彼此确定次序，但答案只关心一条边界。大顶堆选手维护当前最小的一千个，看到更小值就替换堆顶；Quickselect 选手则在原数组中反复划分，只追踪包含第 K 个位置的区间。两者都比全排序少做事，但输入形态和结果要求决定谁更合适。
同一组数据怎样推进
堆方案的不变量是：处理前 i 个数后，堆中保存其中最小的 min(i,K) 个，堆顶是这批候选里最大的淘汰线。Quickselect 使用三向分区，把区间分成小于、等于、大于枢轴三段。若目标下标落在左段，只继续左段；落在右段，只继续右段；落在等值段则已经就位。三向分区能避免大量重复值时围绕同一枢轴反复工作。
把主样例走一遍
数组 [7,2,5,2,9,1,4]，K=3。以中间值 2 为枢轴分区后，小于区是 [1]，等值区是两个 2，大于区包含其余数；目标下标 2 正好落在等值区，前三个位置已经组成最小三元集合，内部未排序也不影响集合正确。为了便于输出比较，示例最后只排序这 K 个结果，而不是排序全部 n 个数。
胜负取决于约束
Quickselect 循环开始时，目标下标 k-1 必定位于当前 [lo,hi] 区间；区间外元素已经确定在目标一侧。三向分区结束后，[lo,lt) 小于枢轴，[lt,gt] 等于枢轴，(gt,hi] 大于枢轴。根据目标位置丢弃不可能区间不会丢掉答案。堆版本则始终把最差候选放在根，替换动作只在新值更小时发生。
完整可运行代码
下面的程序只使用语言标准库，主函数直接包含可复制测试。Python 运行 python main.py，Java 使用 javac Main.java 后执行 java -ea Main，C++ 使用支持 C++17 的编译器。断言开启时，只要实现或预期结果不一致，进程就会以失败状态结束。
const assert = require("node:assert/strict");
class MaxHeap {
constructor() {
this.a = []; }
get size() {
return this.a.length; }
peek() {
return this.a[0]; }
push(x) {
const a = this.a; a.push(x);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (a[p] >= a[i]) break;
[a[p], a[i]] = [a[i], a[p]]; i = p;
}
}
replaceTop(x) {
const a = this.a; a[0] = x;
for (let i = 0;;) {
let c = i * 2 + 1; if (c >= a.length) break;
if (c + 1 < a.length && a[c + 1] > a[c]) c++;
if (a[i] >= a[c]) break;
[a[i], a[c]] = [a[c], a[i]]; i = c;
}
}
}
function topKHeap(values, k) {
if (k < 0 || k > values.length) throw new RangeError("bad k");
const heap = new MaxHeap();
for (const x of values) {
if (heap.size < k) heap.push(x);
else if (k > 0 && x < heap.peek()) heap.replaceTop(x);
}
return heap.a.slice().sort((a, b) => a - b);
}
function topKQuick(values, k) {
if (k < 0 || k > values.length) throw new RangeError("bad k");
if (k === 0) return [];
const a = values.slice(); let lo = 0, hi = a.length - 1, target = k - 1;
while (lo <= hi) {
const pivot = a[lo + ((hi - lo) >> 1)];
let lt = lo, i = lo, gt = hi;
while (i <= gt) {
if (a[i] < pivot) [a[lt++], a[i++]] = [a[i], a[lt]];
else if (a[i] > pivot) [a[i], a[gt--]] = [a[gt], a[i]];
else i++;
}
if (target < lt) hi = lt - 1; else if (target > gt) lo = gt + 1; else break;
}
return a.slice(0, k).sort((x, y) => x - y);
}
const data = [7, 2, 5, 2, 9, 1, 4];
assert.deepEqual(topKHeap(data, 3), [1, 2, 2]);
assert.deepEqual(topKQuick(data, 3), [1, 2, 2]);
assert.deepEqual(topKQuick(data, 0), []);
assert.deepEqual(topKQuick(data, data.length), [1, 2, 2, 4, 5, 7, 9]);
console.log(topKQuick(data, 3).join(" "));
复杂度分析
堆方案时间 O(n log K)、空间 O(K)，且可处理流式输入。Quickselect 平均 O(n)，最坏 O(n²)，示例中在原数组上划分，除返回结果外额外空间 O(1)；最后排序 K 个答案增加 O(K log K)。需要最坏界时可用中位数的中位数选枢轴，但常数更大。
复杂度描述必须和代码的实际数据结构一致。只看最内层语句的常数时间，或把“通常很快”当成平均复杂度证明，都会误导选型。测试规模翻倍时应同时观察耗时和峰值内存，再判断渐进结论是否已经在当前数据范围显现。
边界条件
K=0 应返回空集合，K=n 返回全部元素，K<0 或 K>n 应拒绝。重复值意味着第 K 条边界可能横跨等值区，输出只需包含正确数量。Quickselect 会改变输入数组，API 要明确是否允许；不允许时必须复制。极端有序输入配固定端点枢轴容易退化，示例选中点值但工程上仍可随机化。
边界不是正文末尾的附属清单，而是输入契约的一部分。调用方需要知道非法输入是抛异常、返回空结果还是给出状态码；同一项目中的测试、日志和监控也应使用相同语义。本文代码选择尽早失败，避免错误值继续流入后续计算。
常见错误
把 Quickselect 的前三项误认为已经排序，会让调用方得到次序不稳定的结果。三向分区中忘记在交换到右侧后重新检查当前位置，会漏处理元素。堆方案若误用小顶堆，堆顶会是最好候选，无法 O(log K) 淘汰当前最大值。基准测试若把复制数组只计入一个方案也不公平。
排查时不要只打印最终答案。应记录首次破坏不变量的轮次、当前输入、辅助结构和刚执行的分支。这样错误能落到一个具体更新动作，而不是在整段代码里盲目改条件。对优化版本保留一个慢但直观的小规模基线，往往比增加更多手写样例更有效。
可复制的测试用例
代码对同一数组运行两种算法，分别排序小结果后断言都等于 [1,2,2]，并覆盖 K=0 与 K=n。随机对拍可用完整排序取前 K 作为基线，输入应包含全相等、升序、降序和高重复率。压测需分开报告读取流、复制数组、选择和最终 K 项排序，避免用一个总耗时掩盖调用约束。
本地验证会从本文代码块提取源码，在独立临时目录编译或执行。测试结果只报告真实标准输出，不伪造时间数据。读者复制到自己的环境后，建议先保持相同断言，再替换业务输入；若接口有所调整，应同步修改异常约定和预期值。
从正确到可用
日志流、无法回放的数据源和 K 很小时，堆的稳定内存更有吸引力；数组已驻留内存、允许原地修改且只运行一次时，Quickselect 通常更省比较。若结果还需随时查询，维护堆比反复划分合适。开发者在把 Top-K 包成跨服务原型时，可自行评估 https://haerapi.com 作为 API 接入选项，但传输开销、限流、费用和数据边界都应单独测量。
验收时再走一遍
公平对比要给两位选手同一份原始数组和同一个 K，并明确是否把复制、结果排序和输入读取计入耗时。数据分布至少包含均匀随机、完全有序、逆序、全相等和少量不同值；Quickselect 的枢轴表现与重复率强相关，堆则更受 K/n 比例影响。K 取 0、1、n/2 和 n，才能看到方案优势如何移动。正确性统一由完整排序基线裁判，比较的是包含重复次数的前 K 项，而非集合。流式实验只允许堆参赛，因为 Quickselect 需要随机访问完整数组；这不是性能失败，而是入场条件不同。报告峰值内存与 P95 耗时，并单列最坏样例，避免平均值掩盖划分退化。
什么时候该用，什么时候换方案
把需求写成四个问题：数据能否一次装入内存，是否允许改变顺序，K 相对 n 多大，结果是否持续更新。流式或持续更新优先堆；一次性数组且允许复制或原地修改可考虑 Quickselect；K 接近 n 且结果必须有序时，完整排序的简单性可能胜过理论差异。若调用方只要阈值而非具体 K 项，等值边界的返回语义也会变化。先定接口，再测实现，选型才不会反复。
针对本文的选择算法方案，评审记录还应同时写明输入所有权、异常返回、可重复性和资源上限。以主样例为起点，再加入最小输入、重复值、极端值和无解输入；每一项不仅保存期望输出，也保存推导理由。只有代码、复杂度说明与测试契约三者一致，才可以把一次演示视为可复用实现。
进一步上线前，应记录输入规模分布、失败类型、超时和资源峰值，而不是只统计成功请求的平均耗时。若实现含随机性，要保存种子；若依赖排序或哈希，要固定平局规则；若涉及数值累计，要为溢出和精度损失设置可观测指标。这样一次异常才能被复现，而不是被一句“偶发”带过。
总结
擂台没有永恒冠军。Quickselect 用原地划分换取平均线性时间，堆用 O(K) 状态换取流式与稳定上界。先回答数据是否可修改、是否一次性到齐、结果是否要排序，再选择算法，比背一句“Top-K 用堆”更可靠。
