2022·42 十万数找最小 10 个：全排序到大根堆门槛过滤

本文属于「从暴力解到最优解」专题的第二组，但和前面「真不用优化」的题不同——它是一个反例。总纲判断一道题要不要优化的简单方法是看题面有没有出现「尽可能高效」四个字，这道题确实没有，所以它被归进了第二组的表格。但它的题干里另有一句「要求平均情况下的比较次数尽可能少」——换了个说法，说的是同一件事。**只数关键词是不够的，题面的其它措辞、甚至给定的数据规模本身，都可能悄悄夹带最优性要求。**这道题就是练这份警觉的最佳材料。

题目

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

(1) 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不需要程序实现。 (2) 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

总分 8 分。优化要求就藏在 (1) 问那句「比较次数尽可能少」里——它没有说「时间复杂度尽可能低」，也没有说「尽可能高效」，但「比较次数」正是这道题的计价单位，效果完全一样。另外要注意，(1) 问明确写了「不需要程序实现」，只要把算法思想讲清楚即可；下文仍然给出两版 C 代码，是为了让暴力解和最优解的差别看得更直白，考场上并不需要真的写出来。

第一步：把暴力解写对

n 远大于 10，考场上最直接的反应通常是：把 n 个数全排序，排完前 10 个就是答案。

#include <stdlib.h>

int cmpInt(const void *a, const void *b) { return *(int *)a - *(int *)b; }

// 全排序后取前 10 个：结果一定正确，但排序本身要付出 O(n log n) 次比较
void findMinKBruteForce(int M[], int n, int result[]) {
    int *copy = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) copy[i] = M[i];
    qsort(copy, n, sizeof(int), cmpInt);      // 排序算法内部比较次数 O(n log n)
    for (int i = 0; i < 10; i++) result[i] = copy[i];
    free(copy);
}

复杂度：排序占主导，比较次数 $O (n \log n)$ ；额外拷贝一份数组，空间 $O (n)$ （若原地排序可降到 $O (1)$ ）。

它值多少分

408 算法设计题通常按正确性/最优性两个维度判分（详见总纲），但这道题要格外小心：它把「最优」直接写进了 (1) 问的设问里，(1) 问的两个得分点——「维护大小 10 的大根堆」和「门槛比较机制」——都是围绕具体方法给分的，不是围绕「有没有找对这 10 个数」给分。

结果本身没有问题：全排序一定能找出正确的最小 10 个数，这一点不会错。
但 (1) 问的分基本拿不到：题目解析明确写着——全排序不满足「比较次数尽可能少」，按不达最优处理。你说得再清楚，只要设计思想不是「用一种能让比较次数逼近 n 的方法」，(1) 问的 6 分就落不到手里。
(2) 问同理受牵连：时间复杂度这一问对应的 1 分要求写出 $O (n)$ ——但你实际的算法就是 $O (n \log n)$ ，照实写出 $O (n \log n)$ 只是保住了「复杂度分析与算法一致」这个基本盘，换不来那 1 分；空间那 1 分要求 $O (1)$ ，全排序的拷贝数组也够不上。

这道题和其它「暴力解拿正确性分、丢最优性分」的真题不太一样：那些题里，暴力解的「正确性」是一个独立的、能稳稳拿到手的维度；这道题的判分点几乎全部焊死在「是不是用了能让比较次数最少的方法」上，全排序虽然结果对，但换不来对应的设计分。这也是为什么它被专题选作反例——看着像"随便一个正确算法就有分"的题，实际判分口径比想象中严格。

还有一条稍微体面一点的暴力路线：简单选择排序做 10 趟，每趟从剩余元素里选出最小的放到前面，比较次数约 $10 n$ 。它的常数比全排序小、更贴近"直接奔着 10 个数去"的直觉，题目解析对它的处理也温和一些——只扣 2 分，其余分数仍能拿到。可见暴力解之间也有优劣之分：全排序连"够不着最优"都不体面，选择排序至少是朝着正确方向迈了一步、只是常数因子不够好。

暴力解的浪费在哪

用总纲的三个问题审一遍全排序：

**有没有放着性质不用？——有，而且是最大的浪费。**我们要的只是最小的 10 个数，n 却有十万乃至更多。全排序把这 n 个数从头到尾都排出精确的相对顺序，但题目只要前 10 名，后面 99990 个数之间谁大谁小根本不关心。排序做的事情比题目要求的多太多了——你只想知道谁进前 10，它却把全员的名次都算了出来。

换个角度看：全排序里每次比较，参与的两个数都有可能是"注定进不了前 10"的两个大数——这种比较对最终答案毫无贡献，纯属陪跑。

智慧化改造：大小为 10 的大根堆门槛过滤

浪费找到了：不需要知道后 99990 个数的相对顺序，只需要一个能快速判断"新数能不能挤进前 10"的机制。

标准答案是维护一个大小为 10 的大根堆——注意，是大根堆，不是更符合直觉的小根堆：

用 M 的前 10 个元素建一个大根堆，堆顶 top 是这 10 个数里最大的；
对剩余 n − 10 个元素 v，先与堆顶比较 1 次：若 v ≥ top，v 不可能进前 10，直接跳过；否则用 v 替换堆顶，向下调整堆（ $⌈ \log_{2} 10 ⌉ \approx 4$ 层，约 7 次比较）；
遍历完成，堆里就是最小的 10 个数。

反直觉的地方在于大根堆的堆顶恰好是当前 top-10 中最大的那个，天然就是一道"门槛"：新数只要不比门槛小，就注定进不了前 10，1 次比较即可判掉。n 巨大、k=10 很小，新数能打破门槛、挤进前 10 的概率极低，所以绝大多数元素只经历这 1 次比较就被淘汰，整体期望比较次数

10 \times \log_{2} 10 + \sum_{i = 11}^{n} (1 + \frac{10}{i} \cdot \log_{2} 10) \approx n + O (\log n)

量级是 $O (n)$ ，常数因子接近 1——这正是"比较次数尽可能少"这句话真正想要的东西。

#define K 10

// 大小为 K 的大根堆下沉调整
void siftDown(int heap[], int i, int size) {
    while (1) {
        int largest = i, left = 2 * i + 1, right = 2 * i + 2;
        if (left < size && heap[left] > heap[largest]) largest = left;
        if (right < size && heap[right] > heap[largest]) largest = right;
        if (largest == i) break;
        int tmp = heap[i]; heap[i] = heap[largest]; heap[largest] = tmp;
        i = largest;
    }
}

// 找出 M 中最小的 K 个数，结果放进 heap[0..K-1]（堆结构，未必有序）
void findMinKHeap(int M[], int n, int heap[]) {
    for (int i = 0; i < K; i++) heap[i] = M[i];        // 前 K 个建堆
    for (int i = K / 2 - 1; i >= 0; i--) siftDown(heap, i, K);

    for (int i = K; i < n; i++) {
        if (M[i] < heap[0]) {          // 门槛比较：1 次
            heap[0] = M[i];            // 替换堆顶
            siftDown(heap, 0, K);      // 向下调整
        }
        // 否则 M[i] >= 堆顶，直接跳过，这一轮只花了 1 次比较
    }
}

从暴力解升级过来，两个反直觉点务必记牢：

大根堆不是小根堆：找最小的 k 个，第一反应通常是"小根堆"，但小根堆的堆顶是当前最小值，没法 1 次比较判断"新元素是否比现有 top-k 都大"。只有大根堆的堆顶（top-k 里的最大者）才能当门槛用。
门槛比较是"1 次决定去留"：不是每个新元素都要走"替换 + 下沉"的完整流程，绝大多数元素在门槛比较那一步就出局了，这正是常数因子小的来源。

复杂度：时间 $O (n \log k) = O (n)$ （k = 10 是常数）；空间 $O (k) = O (1)$ ，除入参 M 外只用了大小为 10 的堆数组，与 n 无关。这就是标准答案，(1)(2) 两问的分都能拿到。

两版对照跑一遍

演示数组缩小成十几个数、k 取 4（真题里 k = 10，这里改小只是为了让可视化步骤看得清楚，机制完全一样）。先看全排序版——注意它把整个数组都排出了顺序：

加载可视化中...

再看大根堆门槛版——注意大多数元素只经历了 1 次门槛比较，堆的下沉调整只在少数几次替换时才发生：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应；两版跑完得到的最小 k 个数集合完全一致，只是花的比较次数天差地别。

等价方法与升级空间

简单选择排序 10 趟：每趟 n − 1 次比较，共约 10n 次，常数比堆法大近 10 倍。方向是对的（确实在往"只关心前 10"上靠），题目解析给的是扣 2 分，而不是全排序那种按错处理——同样是暴力解，离最优的距离不一样，判分也不一样。
快速选择（quickselect）：平均 $O (n)$ ，量级上已经够了，但常数大、最坏情况 $O (n^{2})$ ，还需要修改原数组。解析认为思想正确但不是本题最优选择，只给部分分——这是「方法等价但不是当前题目要的那个最优」的典型例子。
小根堆的常见误区：把"找最小 k 个"直觉套成"用小根堆"，会发现堆顶（当前最小值）根本没法充当"新元素能不能进前 k"的判据，这个误区在设计思想那一问按思路错处理，务必记住大根堆才是标准答案。

下一步

在 OJ 上把两版代码都提交跑一遍：ds-2022-42 Top-K 最小值
回到题库看这道题的完整解析与错因：真题库 · 数据结构

2022·42 十万数找最小 10 个：全排序到大根堆门槛过滤 ​

题目 ​

第一步：把暴力解写对 ​

它值多少分 ​

暴力解的浪费在哪 ​

智慧化改造：大小为 10 的大根堆门槛过滤 ​

两版对照跑一遍 ​

等价方法与升级空间 ​

下一步 ​