目录
在之前我们学习堆相关的内容中，小编讲了堆的实现以及堆的应用之一——堆排序，及时堆还有第
二种应用，也就是今天小编要讲的堆在数据结构中很经典的应用场景-堆的TOP-K问题。
1. TOP-K问题
1.1 定义
堆的TOPK问题是数据结构中很经典的应用场景，简单说指的是从大量数据（通常数据量 n 很大）
中，找出最大（或最小）的前 K 个元素（ K 通常远小于 n ）。
- 例如：从100万条成绩中找前100名高分；从海量商品评价中找点赞数前5的评论等。
1.2 思路推导
首先, 我们先明确核心矛盾：数据量大，直接排序不现实
当数据量 n 极大（比如10亿条数据），如果直接对所有数据排序（比如快排），时间复杂是 O
(n log n) ，且需要将所有数据加载到内存，空间成本极高。
而 K 通常很小（比如前100名），我们只关心“最大的前 K 个”，不需要对所有数据排序——这时候
需要更“节俭”的方法：只维护一个能代表“当前候选" top- K "的集合，用这个集合去过滤剩余数
据。
当然最后一句话是怎么理解的呢？我们的目标是找到“所有数据中最大的前K个”，但并不需要一次
性处理所有数据。假设现在有一堆数据，先随便选K个出来，这K个数据就可以作为“临时的top-K”
数据。重要的是看剩下的数据：
- 如果某个剩下的数据比候" top-K "中的数据中最小的那个还小，那它肯定没资格进入" top-K "中
(因为" top-K "里最差的都比不过），所以直接跳过；
- 如果某个剩下的数据比候" top-K "数据中最小的那个大，说明它比" top-K "数据里“最垫底”的更
有资格，这时候就把" top-K "数据里最小的踢出去，让新数据进来——这样" top-K "数据始终保
持着“目前见过的、有可能是" top-K "数据的元素”。
关键在于：" top-K "中数据的大小始终是K，不管总数据量有多大，我们只需要用这K个元素来“守
门”，就能过滤掉所有不可能进入" top-K "数据中的元素。
1.3 与堆的联系
那么, 我们应该如何设计选择这个" top-K "数据集合的？
假设要找“前 K 个最大元素”，" top-K "数据集合需要满足两个条件：
- 集合大小固定为 K （节省空间）；
- 能快速判断新元素是否有资格进入集合（高效筛选）。
而堆的特性恰好适配：假设有一个小堆，堆中有K个数据。这个时候我们就可以把这个小堆看成这
个" top-K "数据集合。
- 小顶堆的堆顶是" top-K "数据集合中最小的元素。如果新元素比堆顶大，说明它比" top-K "数据
集合中最小的元素更优秀，有资格替换掉堆顶，进入" top-K "数据集合中；
- 替换后只需一次“向下调整”（ O(log K) 时间），就能重新维持小顶堆的结构，保证堆顶始终是新
" top-K "数据集合中最小的元素。
简单来说 : 堆的作用，就是让这个" top-K "数据里的“最小元素”能被快速找到（因为小顶堆的堆顶
就是最小的），并且在替换元素后能快速重新整理" top-K "数据（通过向下调整），保证“守门”的
效率。
举个形象点的例子 : 就是“用K个位置当筛子，只留比筛子眼大的，最后筛子里剩下的就是最大的那
批”。
那为什么是“小顶堆”而不是“大顶堆”？
- 找“前 K 大”用小顶堆：堆顶是当前 K 个中最小的，只要新元素比它大，就有资格进入，替换后堆
里始终是“当前已知的前 K 大”；
- 若用大顶堆：堆顶是当前 K 个中最大的，新元素比堆顶小的话，无法判断是否比堆里其他元素大
（比如堆里有 [10,8,5] ，新元素6比10小，但比5大，其实有资格进入，但大顶堆无法通过堆顶判
断）。
同理，找“前 K 小”则用大顶堆，逻辑对称。
简言之，堆解法的推导逻辑是：先抓住“只关心" top-K "数据，无需全排序”的核心需求，再利用堆
的“快速访问最值+高效调整”特性，用最小的空间和时间成本筛选出目标元素。
1.4 代码的实现
void TopK()
{
int k = 0;
printf("请输入K：");
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail!");
exit(1);
}
//找最大的前K个数据，建小堆
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail!");
exit(2);
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}
//minHeap -- 向下调整建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minHeap, i, k);
}
//遍历剩下的n-k个数据，跟堆顶比较，堆顶小替换堆顶元素
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
//X minHeap-top
if (x < minHeap[0])
{
minHeap[0] = x;
AdjustDown(minHeap, 0, k);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
fclose(fout);
}这段代码的逻辑是通过小顶堆求解“前K个最大元素”问题，整体思路和我们之前讨论的一致，整体
逻辑如下：
1. 定义变量与输入K值
int k = 0;
printf("请输入K：");
scanf("%d", &k);- 先定义变量 k ，用于存储要找的“前K个”中的K值。
- 通过 printf 提示用户输入K，再用 scanf 读取用户输入的数值，存到 k 中。
2. 打开数据文件
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail!");
exit(1);
}- 定义文件名 file 为 "data.txt" （存储待处理的大量数据）。
- 用 fopen 以只读方式打开文件，返回文件指针 fout 。
- 如果文件打开失败（ fout 为 NULL ），用 perror 输出错误信息，然后 exit(1) 终止程序。
3. 申请堆空间并读取前K个数据
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail!");
exit(2);
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}- 用 malloc 申请一块能存 k 个整数的内存，作为小顶堆的存储空间，指针 minHeap 指向这块内
存。
- 如果内存申请失败（ minHeap 为 NULL ），输出错误信息并终止程序。
- 用 for 循环从文件中读取前 k 个整数，依次存入 minHeap 中（此时还不是堆，只是普通数组）。
4. 将前K个数据构建为小顶堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minHeap, i, k);
}- 这一步是“构建小顶堆”的核心：从最后一个非叶子节点开始，依次向前对每个节点执行“向下调整”
（ AdjustDown 函数），最终将 minHeap 数组转换成小顶堆。
- 公式 (k-1-1)/2 是计算最后一个非叶子节点的索引（堆的特性：若父节点索引为 i ，左孩子
为 2i+1 ，右孩子为 2i+2 ，反过来可推出父节点索引）。
- AdjustDown 函数的作用是：当某个节点的值大于其孩子时，将它与较小的孩子交换，直到满足
小顶堆的性质（父节点 < 孩子节点）。这在之前堆的实现文章中有详细讲解。
5. 遍历剩余数据并更新堆
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
if (x > minHeap[0])
{
minHeap[0] = x;
AdjustDown(minHeap, 0, k);
}
}- 定义变量 x ，用于存储从文件中读取的后续数据。
- 用 while 循环持续从文件中读取数据（ fscanf 返回 EOF 时表示文件读完），每次读一个整数存
到 x 中。
- 核心逻辑：比较 x 和小顶堆的堆顶（ minHeap[0] ，即当前K个元素中最小的那个）。
- 若 x 比堆顶大（即 x > minHeap[0] ），说明 x 更有资格进入“前K大”，就替换堆顶为 x 。
- 替换后，调用 AdjustDown 从堆顶开始调整，保证 minHeap 仍然是小顶堆。
6. 输出结果并关闭文件
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
fclose(fout);- 遍历小顶堆，用 printf 输出堆中的 k 个元素，这些就是最终找到的“前K个最大元素”。
- 用 fclose 关闭文件，释放资源。
以上便是对于TOP-K问题整个代码的实现。要注意的是在这个代码中要用到向下调整函数。
1.5 复杂度
1. 时间复杂度
以“找前K个最大元素，用小顶堆”为例:
- 步骤1：构建初始堆（前K个元素）
从n个元素中取前K个，构建一个小顶堆。
堆的构建时间复杂度为 O(K)（注意：堆化的时间不是O(K log K)，而是O(K)，因为从底层向上调
整的实际操作次数远少于K log K）。
- 步骤2：遍历剩余元素并更新堆（n-K个元素）
对剩下的（n-K）个元素，每个元素都要与堆顶比较：
- 若不需要替换（新元素≤堆顶）：操作时间为O(1)，可忽略；
- 若需要替换（新元素>堆顶）：需移除堆顶并插入新元素，此时需要对堆进行“向下调整”以维持小
顶堆结构，调整时间为 O(log K)（堆的高度为log K，每次调整最多移动log K次）。
最坏情况下，每个元素都需要调整，总时间为 O((n-K) log K)。
整体时间复杂度为：O(n log K)
2. 空间复杂度
堆解法只需存储K个元素的堆，空间复杂度为 O(K)，远优于全排序的O(n)（需存储所有元素），尤
其适合海量数据场景。因此比其他排序法(全排序)更优，堆解法效率提升显著。
1.6 优势
1. 效率极高，适配大数据
时间复杂度为 O(n log K) ，远优于对所有数据排序的 O(n log n) 。当数据量 n 极大（如百万、亿
级）且 K 较小时（如10、100），效率提升显著，能快速得到结果。
2. 空间占用少，适合内存有限场景
只需维护大小为 K 的堆，无需加载全部数据到内存。对于无法一次性载入内存的海量数据（如TB
级文件），可分批次处理，大幅降低内存压力。
3. 支持动态更新，适配实时场景
当数据动态增加时（如实时产生的用户行为），只需用新数据与当前堆顶比较，即可快速更新
TOP-K结果，无需重新处理全部历史数据，适合实时排行榜等场景。
4. 实现简单，逻辑直观
核心逻辑是“用小顶堆（或大顶堆）做门槛筛选”，思路清晰，容易理解和实现，且堆结构在多数编
程语言中都有现成的数据结构或库支持（如Python的 heapq 模块）。
这些优势让TOPK的堆解法成为处理“海量数据筛选”“实时结果更新”等问题的首选方案。
1.7 应用场景
TOPK问题在实际场景中非常常见，核心是从大量数据中快速筛选出“最相关”“最突出”的少数元素，
典型应用包括：
- 排行榜场景：如电商平台的“销量前10商品”、视频平台的“播放量前5视频”、游戏中的“积分榜前
100玩家”等。
- 数据筛选：从海量日志中提取“错误次数最多的前5类异常”、从用户行为数据中找出“活跃度前20
的用户”。
- 推荐系统：基于用户偏好，从候选池中筛选“最可能感兴趣的前K个内容”（如短视频推荐、商品推
荐）。
- 实时监控：在实时数据流中（如服务器性能指标），快速定位“CPU使用率最高的前3台设备”等关
键信息。
2. 总结
以上便是关于TOP-K问题的所有讲解内容。整体来说这个问题不仅是数据结构中很经典的一类排序
问题，更是为比较排序提供了一种新颖的思路。思路清晰，逻辑流畅，非常值得大家熟练掌握并应
用。最后感谢大家的观看！