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^6sort大概要做两千万次量级的比较运气好能过运气差就是TLE。方案B有序数组插入。先读前M个排好序之后每读一个数如果比当前第M个数大就插入到合适位置并把最后一个挤出去。这个方法的空间是O(M)时间大约是O(N×M)。M很小的时候确实能过比如M10N10^6就是一千万次操作勉强能扛住但M一旦大到1000这个复杂度就彻底不行了。方案C用大小为M的最小堆维护前M大。空间O(M)时间O(N log M)。由于M≤10log M几乎是一个小常数整体复杂度逼近O(N)是最稳的方案。我把三个方案放在一起做了个对比方案空间时间代码量适用场景全量排序O(N)O(N log N)最少N小或内存充足有序数组插入O(M)O(N×M)较短M非常小最小堆维护Top MO(M)O(N log M)中等海量数据、N远大于M表格看下来堆的优势已经很清楚了。不过这里我想多说一句方案B并非完全没用在一些C语言版的PTA题目里M被卡得很小用有序数组插入也能AC。但作为一名刷题的人我更建议直接学堆的写法因为后面遇到的Top K变体题几乎没有第二种通用解。1.3 为什么堆是这道题的最佳答案堆之所以成为这类题的标准答案有三个层面的原因。第一空间占用少。从头到尾只保存M个元素不会因为N是一百万就把内存全部吃掉。这在处理流式数据、海量日志时非常关键因为你可能根本没有办法一次性把所有数据都装入内存。第二时间稳定。每次堆调整只需要O(log M)次比较而M≤10意味着每次调整大约只有三四次比较N10^6也就是几百万次比较运行速度飞快。即使数据量再上一个量级堆方案依然能撑得住。第三它踩准了数据结构的考点。PTA这道题出现在数据结构板块考察目标非常明确你会不会用堆去解决Top K问题。如果还是用sort“硬刚”等于没有掌握堆的典型应用场景。这个知识点在笔试面试中也特别高频后面第4节我会展开讲它的扩展场景。所以刷题不能只求“交上去AC”而是要把每种数据结构适用在什么场景想清楚。这道题正是堆的“最佳教学案例”之一。2. 堆的原理用最小堆维护“最大的M个”2.1 数组下标就能表示完全二叉树堆是一种特殊的完全二叉树。所谓完全二叉树就是除最后一层外每一层都被填满最后一层的节点从左到右连续排列。这种结构最大的好处是不需要用指针直接拿一个一维数组就能存下整棵树。一般我们用1作为堆的起始下标这样写父子和兄弟关系时最直观。下标i的节点它的左孩子下标是2×i右孩子下标是2×i1父亲节点下标是i/2这里i/2是整数除法。举个例子一个大小为5的堆数组下标从1到5值分别是1、2、3、4、5。下标1是根节点下标2和3是它的两个孩子下标4和5是下标2的两个孩子。这棵树的形状非常清晰而且完全不用额外的内存去存指针。如果从0开始存父下标是(i-1)/2左孩子是2i1右孩子是2i2也可以只是会多几个12的细节。我在后面的代码里统一用1下标。2.2 入堆、取堆顶、替换堆顶三个核心操作最小堆的定义是每个节点的值都小于等于它的孩子节点。也就是说根节点heap[1]是整棵堆里最小的值。这个性质特别适合Top K问题。为什么因为我们想保留“最大的M个”。如果这M个数被组织成一个堆堆顶正好是这M个数里面最小的那个。新来一个数x时如果堆还没满直接把x加入堆如果堆已经满了就比较x和堆顶x小于等于堆顶说明x连当前第M大都比不过直接丢弃x大于堆顶说明x有资格进入前M于是把堆顶替换成x再做一次调整让新的最小值重新浮现到堆顶。这里对应三个核心操作操作一入堆push。把新元素放到数组末尾然后不断和父亲比较如果比父亲小就互换。这个过程叫向上调整也常被称为“上浮”。操作二取堆顶top。直接返回heap[1]。操作三替换堆顶并调整poppush。把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, greaterint()); 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, greaterint())把堆排序成降序。因为堆只保证每个节点小于等于孩子并不保证全局有序所以不能直接按数组顺序输出。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); // greaterint 表示小顶堆堆顶是最小值 priority_queueint, vectorint, greaterint 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); } } // 把堆里的数取出来倒序输出就是降序 vectorint 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_queueint, vectorint, greaterint 的三个模板参数分别是元素类型、底层容器、比较方式。默认的priority_queueint是大顶堆堆顶是最大值放在这道题里就全错了因为你需要比较的是“前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.32N等于10^6就是三百多万次比较两者差了将近6倍而且N越大差距越明显。堆方案还有一个额外优势它不需要一次性把全部数据都加载到内存可以边读边处理。这在数据流场景里是刚需因为你根本不知道下一个数据什么时候到也不方便把整个流先存下来再排序。空间上全量排序需要O(N)的数组N10^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_queueint默认是最大堆也就是q.top()取到的是整个堆里最大的元素。放在“维护前M大”的场景里这完全是反的。如果实在想用默认大顶堆也不是不行插入时存负数堆顶就是绝对值最小的负数等价于原数里的最小值。但这样会引入符号转换不直观不建议。更稳妥的写法就是明确写出三个模板参数priority_queueint, vectorint, greaterint 。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经典题目的拆解留言告诉我我再接着写。
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^6sort大概要做两千万次量级的比较运气好能过运气差就是TLE。方案B有序数组插入。先读前M个排好序之后每读一个数如果比当前第M个数大就插入到合适位置并把最后一个挤出去。这个方法的空间是O(M)时间大约是O(N×M)。M很小的时候确实能过比如M10N10^6就是一千万次操作勉强能扛住但M一旦大到1000这个复杂度就彻底不行了。方案C用大小为M的最小堆维护前M大。空间O(M)时间O(N log M)。由于M≤10log M几乎是一个小常数整体复杂度逼近O(N)是最稳的方案。我把三个方案放在一起做了个对比方案空间时间代码量适用场景全量排序O(N)O(N log N)最少N小或内存充足有序数组插入O(M)O(N×M)较短M非常小最小堆维护Top MO(M)O(N log M)中等海量数据、N远大于M表格看下来堆的优势已经很清楚了。不过这里我想多说一句方案B并非完全没用在一些C语言版的PTA题目里M被卡得很小用有序数组插入也能AC。但作为一名刷题的人我更建议直接学堆的写法因为后面遇到的Top K变体题几乎没有第二种通用解。1.3 为什么堆是这道题的最佳答案堆之所以成为这类题的标准答案有三个层面的原因。第一空间占用少。从头到尾只保存M个元素不会因为N是一百万就把内存全部吃掉。这在处理流式数据、海量日志时非常关键因为你可能根本没有办法一次性把所有数据都装入内存。第二时间稳定。每次堆调整只需要O(log M)次比较而M≤10意味着每次调整大约只有三四次比较N10^6也就是几百万次比较运行速度飞快。即使数据量再上一个量级堆方案依然能撑得住。第三它踩准了数据结构的考点。PTA这道题出现在数据结构板块考察目标非常明确你会不会用堆去解决Top K问题。如果还是用sort“硬刚”等于没有掌握堆的典型应用场景。这个知识点在笔试面试中也特别高频后面第4节我会展开讲它的扩展场景。所以刷题不能只求“交上去AC”而是要把每种数据结构适用在什么场景想清楚。这道题正是堆的“最佳教学案例”之一。2. 堆的原理用最小堆维护“最大的M个”2.1 数组下标就能表示完全二叉树堆是一种特殊的完全二叉树。所谓完全二叉树就是除最后一层外每一层都被填满最后一层的节点从左到右连续排列。这种结构最大的好处是不需要用指针直接拿一个一维数组就能存下整棵树。一般我们用1作为堆的起始下标这样写父子和兄弟关系时最直观。下标i的节点它的左孩子下标是2×i右孩子下标是2×i1父亲节点下标是i/2这里i/2是整数除法。举个例子一个大小为5的堆数组下标从1到5值分别是1、2、3、4、5。下标1是根节点下标2和3是它的两个孩子下标4和5是下标2的两个孩子。这棵树的形状非常清晰而且完全不用额外的内存去存指针。如果从0开始存父下标是(i-1)/2左孩子是2i1右孩子是2i2也可以只是会多几个12的细节。我在后面的代码里统一用1下标。2.2 入堆、取堆顶、替换堆顶三个核心操作最小堆的定义是每个节点的值都小于等于它的孩子节点。也就是说根节点heap[1]是整棵堆里最小的值。这个性质特别适合Top K问题。为什么因为我们想保留“最大的M个”。如果这M个数被组织成一个堆堆顶正好是这M个数里面最小的那个。新来一个数x时如果堆还没满直接把x加入堆如果堆已经满了就比较x和堆顶x小于等于堆顶说明x连当前第M大都比不过直接丢弃x大于堆顶说明x有资格进入前M于是把堆顶替换成x再做一次调整让新的最小值重新浮现到堆顶。这里对应三个核心操作操作一入堆push。把新元素放到数组末尾然后不断和父亲比较如果比父亲小就互换。这个过程叫向上调整也常被称为“上浮”。操作二取堆顶top。直接返回heap[1]。操作三替换堆顶并调整poppush。把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, greaterint()); 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, greaterint())把堆排序成降序。因为堆只保证每个节点小于等于孩子并不保证全局有序所以不能直接按数组顺序输出。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); // greaterint 表示小顶堆堆顶是最小值 priority_queueint, vectorint, greaterint 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); } } // 把堆里的数取出来倒序输出就是降序 vectorint 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_queueint, vectorint, greaterint 的三个模板参数分别是元素类型、底层容器、比较方式。默认的priority_queueint是大顶堆堆顶是最大值放在这道题里就全错了因为你需要比较的是“前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.32N等于10^6就是三百多万次比较两者差了将近6倍而且N越大差距越明显。堆方案还有一个额外优势它不需要一次性把全部数据都加载到内存可以边读边处理。这在数据流场景里是刚需因为你根本不知道下一个数据什么时候到也不方便把整个流先存下来再排序。空间上全量排序需要O(N)的数组N10^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_queueint默认是最大堆也就是q.top()取到的是整个堆里最大的元素。放在“维护前M大”的场景里这完全是反的。如果实在想用默认大顶堆也不是不行插入时存负数堆顶就是绝对值最小的负数等价于原数里的最小值。但这样会引入符号转换不直观不建议。更稳妥的写法就是明确写出三个模板参数priority_queueint, vectorint, greaterint 。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经典题目的拆解留言告诉我我再接着写。
