企业官网建设流程全解析

PTA上的“7-1 寻找大富翁”，是数据结构练习里非常经典的一道题。我第一次做它的时候，第一反应是：把所有人的年收入读进数组，sort一遍，然后输出前M个，完事。结果一提交，超时的红色提示直接教我做人了。后来才意识到，这道题表面在讲富豪排行榜，实际考的是堆，而且是Top K问题最典型的应用场景。下面我就按自己的做题思路，把题意拆解、堆的原理、代码实现、复杂度优化到常见坑位，完整过一遍。不管你是正在刷PTA的学生、准备面试的求职者，还是日常要处理“海量数据里取前N条”需求的开发，这篇应该都能用得上。

1. 题意拆解：富豪榜背后的Top K问题

1.1 题面在说什么

“寻找大富翁”这道题的题面一般这样叙述：有一份富豪榜数据，给出一共N个人的年收入，让你找出收入排名前M位的人，并按降序把收入值输出。输入的第一行是两个正整数N和M，第二行是N个整数，每个整数代表一个人的年收入。N能到10^6这个量级，M一般不超过10，甚至更小。输出要求是在一行内按降序输出前M大的收入值，数字之间用空格分隔，行尾不能有多余空格；如果M大于N，就把N个人的收入全部输出。

这道题乍一看非常简单，因为排序在编程里是标配动作。但仔细看约束就会发现，N可以到一百万，这意味着如果一上来就sort整个数组，时间复杂度是O(N log N)，在PTA那种严格时限下，这个复杂度有可能会踩线，甚至直接超时。而且，题目的考点显然不是“你会不会用sort”，而是“遇到海量数据时，能不能想清楚M很小这个关键约束，从而用更小的代价去维护答案”。

这里有一个核心约束非常值得注意：M很小。既然我们只需要前M大，就没有必要对全部N个元素排序。这个“只取前K个大小的问题”，就是经典的Top K问题。搞明白这一点，这道题就成功了一半：它不是在考你排序，而是在考你数据结构里的堆。

1.2 三种常规方案的对比

在想到“用堆”之前，大多数人的思路会在这几个方案里打转。

方案A：全量排序。读入所有数，sort，然后输出前M个。优点是代码最短、理解最简单；缺点是要存下N个数，排序时间O(N log N)。如果N是10^6，sort大概要做两千万次量级的比较，运气好能过，运气差就是TLE。

方案B：有序数组插入。先读前M个，排好序；之后每读一个数，如果比当前第M个数大，就插入到合适位置并把最后一个挤出去。这个方法的空间是O(M)，时间大约是O(N×M)。M很小的时候确实能过，比如M=10，N=10^6，就是一千万次操作，勉强能扛住；但M一旦大到1000，这个复杂度就彻底不行了。

方案C：用大小为M的最小堆维护前M大。空间O(M)，时间O(N log M)。由于M≤10，log M几乎是一个小常数，整体复杂度逼近O(N)，是最稳的方案。

我把三个方案放在一起做了个对比：

表格看下来，堆的优势已经很清楚了。不过这里我想多说一句：方案B并非完全没用，在一些C语言版的PTA题目里，M被卡得很小，用有序数组插入也能AC。但作为一名刷题的人，我更建议直接学堆的写法，因为后面遇到的Top K变体题，几乎没有第二种通用解。

1.3 为什么堆是这道题的最佳答案

堆之所以成为这类题的标准答案，有三个层面的原因。

第一，空间占用少。从头到尾只保存M个元素，不会因为N是一百万就把内存全部吃掉。这在处理流式数据、海量日志时非常关键，因为你可能根本没有办法一次性把所有数据都装入内存。

第二，时间稳定。每次堆调整只需要O(log M)次比较，而M≤10，意味着每次调整大约只有三四次比较，N=10^6也就是几百万次比较，运行速度飞快。即使数据量再上一个量级，堆方案依然能撑得住。

第三，它踩准了数据结构的考点。PTA这道题出现在数据结构板块，考察目标非常明确：你会不会用堆去解决Top K问题。如果还是用sort“硬刚”，等于没有掌握堆的典型应用场景。这个知识点在笔试面试中也特别高频，后面第4节我会展开讲它的扩展场景。

所以，刷题不能只求“交上去AC”，而是要把每种数据结构适用在什么场景想清楚。这道题正是堆的“最佳教学案例”之一。

2. 堆的原理：用最小堆维护“最大的M个”

2.1 数组下标就能表示完全二叉树

堆是一种特殊的完全二叉树。所谓完全二叉树，就是除最后一层外，每一层都被填满，最后一层的节点从左到右连续排列。这种结构最大的好处是：不需要用指针，直接拿一个一维数组就能存下整棵树。

一般我们用1作为堆的起始下标，这样写父子和兄弟关系时最直观。下标i的节点，它的左孩子下标是2×i，右孩子下标是2×i+1，父亲节点下标是i/2，这里i/2是整数除法。

举个例子，一个大小为5的堆，数组下标从1到5，值分别是1、2、3、4、5。下标1是根节点，下标2和3是它的两个孩子，下标4和5是下标2的两个孩子。这棵树的形状非常清晰，而且完全不用额外的内存去存指针。如果从0开始存，父下标是(i-1)/2，左孩子是2i+1，右孩子是2i+2，也可以，只是会多几个+1+2的细节。我在后面的代码里统一用1下标。

2.2 入堆、取堆顶、替换堆顶三个核心操作

最小堆的定义是：每个节点的值都小于等于它的孩子节点。也就是说，根节点heap[1]是整棵堆里最小的值。这个性质特别适合Top K问题。

为什么？因为我们想保留“最大的M个”。如果这M个数被组织成一个堆，堆顶正好是这M个数里面最小的那个。新来一个数x时：

• 如果堆还没满，直接把x加入堆；
• 如果堆已经满了，就比较x和堆顶：
  • x小于等于堆顶，说明x连当前第M大都比不过，直接丢弃；
  • x大于堆顶，说明x有资格进入前M，于是把堆顶替换成x，再做一次调整，让新的最小值重新浮现到堆顶。

这里对应三个核心操作：

操作一：入堆（push）。把新元素放到数组末尾，然后不断和父亲比较，如果比父亲小就互换。这个过程叫向上调整，也常被称为“上浮”。

操作二：取堆顶（top）。直接返回heap[1]。

操作三：替换堆顶并调整（pop+push）。把heap[1]换成新值，然后把它和孩子中较小的那个比较，如果比孩子大就互换，一路向下走到合适位置。这个过程叫向下调整，也叫“下沉”。

举个例子：堆里已经有5个数，分别是100、90、80、70、60，且60作为最小值待在堆顶。这时新来了85。因为85大于堆顶60，所以把堆顶替换成85，然后向下调整，最终堆里的元素变成100、90、85、70、80之类的组合，总之最小的那个重新被顶到堆顶。全程只需要O(log 5)也就是两三次比较，非常快。

2.3 手写堆还是直接用优先队列

C++里，priority_queue的底层实现就是堆。很多刷题党习惯直接调STL，这没问题，笔试面试也能用。但我想提醒一句：如果你还在上数据结构课、还在刷PTA，最好先能手写堆，再用STL。

手写堆能让你真正理解向上调整和向下调整的过程，而不是把priority_queue当成一个“黑盒”。有些考试或面试会直接要求“手写一个小顶堆”或“解释priority_queue的底层是什么”，没写过的话很容易卡壳。而且手写堆的代码量也不大，真的吃透了，每次都自己写反而更踏实。

当然，如果追求效率，在实际工程里直接使用STL的priority_queue就非常合适，稳定且不容易出错。两种写法下面都给出完整代码和讲解。

3. 代码实现：两种写法逐步拆解

3.1 手写小顶堆版本

我先给一版手写堆的完整代码，注释尽量写详细，方便照着敲。

#include <cstdio> #include <algorithm> #include <functional> using namespace std; const int MAXM = 15; // M <= 10，留一点余量 int heap[MAXM]; // 堆数组，下标从1开始 int sz = 0; // 当前堆内元素个数 // 向下调整：把小顶堆中下标为 i 的元素下沉到合适位置 void downAdjust(int i) { int j = i * 2; // j 先指向左孩子 while (j <= sz) { if (j + 1 <= sz && heap[j + 1] < heap[j]) { j = j + 1; // 如果右孩子更小，就指向右孩子 } if (heap[i] <= heap[j]) { break; // 父亲已经比孩子小，不用再调 } swap(heap[i], heap[j]); i = j; // 继续向下处理 j = i * 2; } } int main() { int N, M; scanf("%d%d", &N, &M); for (int i = 0; i < N; i++) { int x; scanf("%d", &x); if (sz < M) { // 堆没满，直接入堆，向上调整 heap[++sz] = x; int cur = sz; while (cur > 1 && heap[cur] < heap[cur / 2]) { swap(heap[cur], heap[cur / 2]); cur /= 2; } } else if (x > heap[1]) { // 新元素比堆顶大，替换堆顶并向下调整 heap[1] = x; downAdjust(1); } } // 堆内元素现在是前 M 大，但堆本身不是全局有序的，排序后输出 sort(heap + 1, heap + 1 + sz, greater<int>()); for (int i = 1; i <= sz; i++) { if (i > 1) printf(" "); printf("%d", heap[i]); } printf("\n"); return 0; }

几个实现细节需要特别注意：

• const int MAXM = 15是因为M最大是10，堆最多存10个元素，下标从1开始的话数组长度15足够。有人习惯开成1000005，那其实是没理解“只存M个”的设计思路。
• 入堆时的向上调整，不需要单独写函数，一个while循环就够了。
• 最后用sort(heap + 1, heap + 1 + sz, greater<int>())把堆排序成降序。因为堆只保证每个节点小于等于孩子，并不保证全局有序，所以不能直接按数组顺序输出。

3.2 STL优先队列极简版本

如果你的目标是快速AC，用STL的优先队列是效率最高的写法。

#include <cstdio> #include <queue> #include <vector> #include <functional> #include <algorithm> using namespace std; int main() { int N, M; scanf("%d%d", &N, &M); // greater<int> 表示小顶堆：堆顶是最小值 priority_queue<int, vector<int>, greater<int> > q; for (int i = 0; i < N; i++) { int x; scanf("%d", &x); if ((int)q.size() < M) { q.push(x); } else if (x > q.top()) { q.pop(); q.push(x); } } // 把堆里的数取出来，倒序输出就是降序 vector<int> ans; while (!q.empty()) { ans.push_back(q.top()); q.pop(); } for (int i = (int)ans.size() - 1; i >= 0; i--) { if (i != (int)ans.size() - 1) printf(" "); printf("%d", ans[i]); } printf("\n"); return 0; }

这段代码有两个关键点：

第一，priority_queue<int, vector<int>, greater<int> >的三个模板参数分别是元素类型、底层容器、比较方式。默认的priority_queue<int>是大顶堆，堆顶是最大值，放在这道题里就全错了，因为你需要比较的是“前M大的最小值”，而不是最大值。这是新手最容易踩的坑，后面第5节还会单独说。

第二，priority_queue没有提供直接替换堆顶的操作，所以必须pop再push。这两个操作都是O(log M)，性能上比手写堆的“替换+向下调整”略多一次常数上的开销，但完全可以忽略。

3.3 输出顺序与边界处理

输出是这道题里最容易“阴沟翻船”的地方。

第一个细节是行末不能有多余空格。我习惯用“前导空格法”：从第二个元素开始，每次输出前先打一个空格，再输出数字。这样无论有多少个元素，最后都不会多出空格。

第二个细节是降序输出。堆里存的是前M大的元素，但顺序是乱的。手写堆版用sort直接排成降序；STL版里先全部取到ans，再倒序输出。两者效果一样。

第三个细节是边界判断。如果ans为空，ans.size() - 1由于无符号整型会变成一个很大的数，循环条件就容易出错。稳妥做法是先把size()强转为int，比如我上面写的(int)ans.size() - 1，当大小为0时就是-1，循环直接不进入，不会越界访问。

4. 性能分析：它到底快在哪里

4.1 复杂度到底快在哪

全量排序的时间复杂度是O(N log N)。N等于10^6时，log2(N)大约20，也就是说要做约两千万次量级的比较。如果N再大一个数量级，比如一亿，这个数字就变成二十六亿，直接不可接受。

堆方案的时间复杂度是O(N log M)。M等于10时，log2(M)大约3.32，N等于10^6就是三百多万次比较，两者差了将近6倍，而且N越大差距越明显。堆方案还有一个额外优势：它不需要一次性把全部数据都加载到内存，可以边读边处理。这在数据流场景里是刚需，因为你根本不知道下一个数据什么时候到，也不方便把整个流先存下来再排序。

空间上，全量排序需要O(N)的数组，N=10^6就已经是4MB的int数组，问题不大，但不优雅；堆方案只存M个数，几十个字节就能搞定。虽然PTA这道题的内存限制通常比较宽松，但“用多少存多少”本身就是好的设计习惯，在真实系统里更是如此。

4.2 输入优化：scanf、关同步与自定义快读

PTA的时限经常卡得很死，有些题算法对了，结果因为输入输出太慢照样超时。这道题N是10^6，如果代码里用的是cin且没有关闭同步，很容易在IO上多吃几十毫秒。

标准做法有两个：

• 直接用scanf和printf，这是最简单粗暴的提速方式；
• 如果坚持用cin/cout，就加上这两行：

  ios::sync_with_stdio(false); cin.tie(0);

如果这还不够，还可以手写一个快读函数：

int readInt() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x * f; }

快读的原理很简单：用getchar逐个字符读，手动转成数字，再跳过空白符。它比scanf快的原因是省掉了格式解析的额外开销。在N达到10^6甚至更大时，这一点点差距可能就决定你是AC还是TLE。

不过也别矫枉过正。代码简洁性同样重要，我一般是先写scanf版本，如果PTA时限确实紧张，再换快读。

4.3 从富豪榜到真实业务场景

“寻找大富翁”是一个典型的Top K场景。把它抽象出来，你会发现很多现实问题都能套进去：

• 海量日志里找出报错次数最多的前50个IP；
• 电商平台统计销量最高的前100件商品；
• 搜索引擎从千万篇文档中找热门关键词；
• 实时交易流里维护价格最高的前10个订单。

这些场景共同点是：数据量可能非常大，甚至源源不断，没法全部存下来，但你只需要维护一个很小的“排名表”。这时候，堆几乎是最省力的数据结构。

更进一步，Top K的思路还能扩展出很多花样：

• 找“最频繁的K个元素”，可以先建哈希表统计频率，再用小顶堆维护频率最高的K个；
• 数据流的中位数，可以用“大顶堆+小顶堆”两个堆解决；
• 多路归并、定时任务调度，底层也常常用堆。

所以这道题虽然只是PTA题库里的一道小题，背后牵出的内容却可以一路延伸到算法面试和系统设计。这也是我建议大家认真研究它的原因。

5. 踩坑记录与高频问题

5.1 M大于N，堆不满怎么办

有一种情况很多人会漏：题面没有保证M一定小于N。如果M等于10而N等于5，那排名前10位其实只有这5个人，应该把所有5个人的收入按降序输出。

上面给出的两种代码都能自动处理这种情况，因为堆里最终有多少个元素，取决于实际入堆的次数。但如果你用的是“先sort全部再输出前M个”的写法，M大于N时就会越界或者乱输出，这是sort版本一个很大的潜在bug。所以建议直接用堆，它天然规避了这个问题。

5.2 优先队列默认是大顶堆，别搞反

我见过不少同学把priority_queue用得挺熟，但真的做Top K时容易忽略：priority_queue<int>默认是最大堆，也就是q.top()取到的是整个堆里最大的元素。放在“维护前M大”的场景里，这完全是反的。

如果实在想用默认大顶堆，也不是不行：插入时存负数，堆顶就是绝对值最小的负数，等价于原数里的最小值。但这样会引入符号转换，不直观，不建议。更稳妥的写法就是明确写出三个模板参数：priority_queue<int, vector<int>, greater<int> >。

5.3 行末空格与空输出

做题时输出格式经常被忽略。PTA对格式要求严格，多一个空格、少一个换行都可能报错。我建议从一开始就养成“格式无小事”的习惯：

• 用“前导空格法”，从第二个元素开始先在前面输出一个空格，再输出数字，保证行尾永远没有多余空格；
• 如果结果为空，就直接输出换行，或者什么都不输出，但一定不能访问空容器中的元素。

还有一个小细节：PTA有时要求输出后换行，有时不要求。我习惯多输出一个换行，评测通常会忽略行尾空白，一般不会扣分。

5.4 M为0这类极端输入

M为0在数学上意味着一个都不输出。虽然题面输入一般不会出现这种情况，但如果你把这道题扩展成通用的Top K工具函数，就要考虑：

• 堆永远不会被填满；
• 最终输出应为空；
• 代码里的排序、遍历、取堆顶这些操作都需要跳过。

我在写通用工具时，会在一开始就加一层保护判断：if (M <= 0) return 0;。虽然是边角料，但多写这一行能避免不少麻烦，也让代码更健壮。

最后再分享点个人体会。这道题我第一次刷的时候，用的是sort大法，交上去超时才认真研究堆。后来在几家公司的笔试题里，我又看到了几乎一模一样的变体：不是“富豪榜”，就是“点击率最高的页面”“下载量最大的资源”，核心无一例外都是Top K。现在遇到这类问题，我脑子里第一反应就是“维护一个大小为K的最小堆”，比什么都靠谱。

如果你也在刷PTA，建议把这道题的两种写法都敲一遍。手写堆那版，敲完最好能默写出来，因为向上调整、向下调整这两段代码在后面的堆排序、优先队列做题中会反复用到。熟练之后再用STL版本提速也不迟。数据结构就是这样，光看不动手，永远记不牢。

多的不说了，去把这题AC了再说。后面想看堆排序、双堆求中位数，或者其他PTA经典题目的拆解，留言告诉我，我再接着写。