题目

现有 n（n > 100000）个数保存在一维数组 M 中，需要查找 M 中最小的 10 个数，请回答下列问题：

(1) 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不需要程序实现。

(2) 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

解析

(1) 算法思想

答案：维护一个大小为 10 的大根堆，遍历 M 中所有 n 个元素，让堆里始终保留"目前看到的最小 10 个数"。

具体流程：

1. 用 M 的前 10 个元素建一个大根堆（堆顶是这 10 个里最大的，记为 top）；
2. 对剩余 n − 10 个元素 v 逐个处理：
   • 与堆顶 top 比较 1 次：若 v ≥ top，直接跳过（v 不可能进 top-10）；
   • 否则用 v 替换堆顶，向下调整堆（最多 层调整，约 7 次比较）；
3. 遍历完成，堆里就是最小的 10 个数。

编者注（生僻术语）：直觉上"找最小的 k 个"应该用小根堆，这里反而用大根堆——因为我们要快速判断"新元素能不能挤进 top-k"。大根堆的堆顶是 top-k 中最大的那个，它是"门槛"：新元素只要 ≥ 门槛就一定不在 top-k 里，1 次比较即可淘汰；若 < 门槛则替换它（让新的最大者作为新门槛）。这是 top-k 问题的标准 trick，记下来。

为什么平均比较次数最少？

绝大多数元素只与堆顶比 1 次就被淘汰（n 大、k 小，新元素是 top-k 的概率极低，期望 ≈ k/i）。整体期望比较次数：

第一项是建堆，第二项里 1 是"门槛比较"必做、 是"替换+下沉"的期望代价（i 越大，新元素打破门槛的概率越低）。整个量级是 O(n)，常数因子接近 1。

对比其它思路：

• 全排序后取前 10：O(n log n)，比较次数远多于堆法；
• 简单选择排序前 10 趟：每趟 n − 1 比较，共约 10n 次比较，常数比堆法大近 10 倍；
• 快速选择（quickselect）：平均 O(n) 但常数大、最坏 O(n²)，且需要修改原数组，工程上不如堆法稳。

(2) 复杂度分析

• 时间复杂度 （k = 10 视为常数）：建堆 O(k log k)；后续每个元素 1 次门槛比较 + 至多 O(log k) 次下沉调整；总比较次数 ≈ n + 常数。
• 空间复杂度 ：除入参 M 外，只用了大小为 k = 10 的堆数组，与 n 无关。