第 272 题：实现TopK推荐，基于堆与快速选择的比较。
题目
实现TopK推荐，基于堆与快速选择的比较。
完整讲解
一、TopK 问题
- 从 $n$ 个数中取最大的 K 个（或最小的 K 个）。推荐中常对候选打分后取 TopK 展示。
二、基于堆
- 思路：维护大小为 K 的最小堆（求最大 K 个）。遍历时若当前值大于堆顶则弹出堆顶、加入当前值；最终堆内即为最大 K 个。时间复杂度 $O(n \log K)$，空间 $O(K)$。
- 特点：不需一次读入全部数据，适合流式；$K \ll n$ 时很省空间与时间。
三、基于快速选择（QuickSelect）
- 思路：借鉴快排的 partition，选 pivot 将数组分为「大于 pivot」与「小于 pivot」；若「大于」一侧个数 $\ge K$ 则在该侧递归找 TopK，否则在另一侧找 TopK - 多出的个数。期望时间 $O(n)$，最坏 $O(n^2)$，可随机 pivot 优化期望。
- 特点：原地、期望线性；但需随机访问且不适合流式。若 K 很小，堆更实用；K 接近 n 时快速选择有优势。
四、比较与选用
- 流式/大数据：用堆，$O(n\log K)$。
- 小 K、内存紧：堆。
- 中等 n、可随机访问、要严格 $O(n)$ 期望：快速选择。实际推荐服务中多为「打分后取 TopK」，若候选已在一台机内存，两种均可；分布式时每分片取局部 TopK 再多路归并（堆）得到全局 TopK。
面试要点
- 能写出堆维护 TopK 的流程与复杂度 $O(n\log K)$；能说明快速选择思路与期望 $O(n)$。
- 能根据场景（流式、K 大小、是否可随机访问）选择实现方式。
记忆要点
- TopK：堆=大小为 K 的最小堆，$O(n\log K)$，适合流式；快速选择=partition 递归，期望 $O(n)$，适合可随机访问。
- 分布式：分片局部 TopK + 多路归并。