数据结构（C语言篇）：（十三）堆的应用-EW帮帮网

前言

堆作为一种高效且灵活的树形结构，在算法设计与优化中扮演着重要角色。其独特的性质——完全二叉树形态与父子节点间的有序性，使得堆能够以对数级时间复杂度动态维护极值，从而为两类经典问题提供优雅解决方案：堆排序利用大顶堆或小顶堆实现无需递归的原地排序，将时间复杂度稳定控制在O(nlogn)；而TOP-K问题则通过堆的极值筛选特性，在海量数据场景下以O(nlogk)的代价快速定位关键元素。无论是排序场景的性能平衡，还是大数据处理的效率优化，堆结构的应用都展现出算法设计与工程实践的深度结合。本文将系统解析这两类问题的技术实现与核心思想。下面就让我们正式开始吧！

一、堆排序

1.1 版本一：基于已有数组建堆、取堆顶元素完成排序

1.1.1 实现逻辑

创建并初始化堆：定义HP类型的堆变量hp，通过HPInit初始化。
构建堆：遍历数组arr，通过HPPush将每个元素插入堆中（插入过程会自动维护堆的性质）。
提取堆顶元素：循环从堆中获取堆顶元素（HPTop），依次存入原数组arr，然后通过HPPop删除堆顶元素。
销毁堆：排序完成后调用HPDesTroy释放堆占用的资源。

完整代码如下所示：

//堆排序----这不是实际的堆排序
void HeapSort01(int* arr,int n)
{
	HP hp;//-----使用数据结构-堆
	HPInit(&hp);
	//调用push将数组中的数据放入到堆中
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);
	}
	int i = 0;
	while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		arr[i++] = top;
		HPPop(&hp);
	}
	HPDesTroy(&hp);
}

1.1.2 底层原理

排序过程的本质是这样的：

若使用小堆：每次提取的堆顶是当前剩余元素的最小值，依次存入数组会得到升序结果
若使用大堆：每次提取的堆顶是当前剩余元素的最大值，依次存入数组（需从后往前存）会得到升序结果

这种堆排序方法的整体时间复杂度为，时间复杂度的计算主要需要考虑下面两种操作：

构建堆：n次HPPush，每次，总复杂度
提取元素：n次HPTop（）和HPPop（），总复杂度。

1.1.3 应用示例

假设堆为小堆（AdjustUp和AdjustDown均按小堆逻辑实现），则应用示例如下所示：

// 假设已实现HPTop函数（获取堆顶元素）
HPDataType HPTop(HP* php) {
    assert(php && !HPEmpty(php));
    return php->arr[0];
}

// 排序示例
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    HeapSort01(arr, n);
    
    // 输出排序结果（升序）
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // 输出：1 1 2 3 4 5 6 9
    }
    return 0;
}

1.1.4 执行流程

以数组[3, 1, 2]为例，执行流程如下所示：

（1）初始化堆：HPInit(&hp)创建空堆。

（2）元素入堆：

插入 3：堆为[3]；
插入 1：经AdjustUp调整后堆为[1, 3]；
插入 2：经AdjustUp调整后堆为[1, 3, 2]（小堆性质：1≤3 且 1≤2）。

（3）元素出堆存回数组：

第一次：HPTop获取 1，存入arr[0]，HPPop后堆变为[2, 3]；
第二次：HPTop获取 2，存入arr[1]，HPPop后堆变为[3]；
第三次：HPTop获取 3，存入arr[2]，HPPop后堆为空。

（4）销毁堆：HPDesTroy(&hp)释放资源，排序完成，数组变为[1, 2, 3]

为什么说这种堆排序“不是实际的堆排序”呢？

这种方法实现的堆排序与标准堆排序的核心区别在于空间效率：

标准堆排序是直接在原数组上构建堆（原地建堆）的，通过 "堆顶与末尾元素交换 + 向下调整" 实现排序，不需要额外的堆结构，空间复杂度为；

而这种堆排序需要额外创建一个堆结构存储所有元素，空间复杂度为，本质是 "借助堆的特性实现排序"，而非严格意义上的原地堆排序。

除此之外，标准堆排序的建堆过程是通过AdjustDown从后往前调整（时间复杂度为），而该函数通过HPPush建堆（时间复杂度为），建堆效率是比较低的。

1.2 版本二：原地排序 —— 标准堆排序

标准堆排序的核心思路在于：数组建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据。

1.2.1 实现逻辑

标准堆排序的核心操作主要分为两个阶段：

（1）建堆阶段：

首先从最后一个非叶子节点（从索引（n-1-1）/ 2）开始，向前遍历至根节点；

然后对于每个结点执行AdjustDown（向下调整），将无序数组转换为堆（默认实现为大堆，便于升序排序）。

（2）排序阶段：

定义end指向当前堆的最后一个元素（初始为n-1）；
循环交换堆顶（索引0，当前最大值）与end位置的元素，将最大值 "沉" 到数组末尾；
对新堆顶（原end位置元素）执行AdjustDown，调整范围为[0, end)（排除已排好的末尾元素）；
减小end，重复操作直到end为0（所有元素排序完成）。

完整代码的实现如下：

//堆排序————使用的是堆结构的思想 n * logn
void HeapSort(int* arr, int n)
{
	//向下调整算法——建堆n
	for (int i = (n - 1 - 1)/2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	////向上调整算法建堆n*logn
	//for (int i = 0; i < n; i++)
	//{
	//	AdjustUp(arr, i);
	//}

	//n*logn
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);//logn
		end--;
	}
}

1.2.2 底层原理

建堆的选择：

标准堆排序优先使用AdjustDown从后往前建堆，时间复杂度为；

上述代码中的AdjustUp从前往后建堆，时间复杂度为，因此前者更高效；

建堆选择大堆的原因：大堆的堆顶是最大值，每次交换后可将最大值放到数组末尾，直接形成升序。

原地排序的实现：

无需额外空间，直接在原数组上通过索引操作实现堆结构（利用完全二叉树的父子节点索引关系）；

end变量的作用是划分 "未排序的堆区域" 和 "已排序的末尾区域"，随着循环逐渐缩小堆区域。

1.2.3 时间复杂度计算

分析如下：

第1层，有个结点，交换到根结点后，需要向下移动0层；

第2层，有个结点，交换到根结点后，需要向下移动1层；

第3层，有个结点，交换到根结点后，需要向下移动2层；

……

第h层，有个结点，交换到根结点后，需要向下移动h-1层。

由此我们可以发现，堆排序第二个循环中的向下调整与建堆中的向上调整算法的时间复杂度计算是一致的，故在这博主就不再过多赘述了。大家如果感兴趣的话可以去看看我上一期的博客。

最终可以计算得到堆排序的时间复杂度为

二、TOP-K问题

TOP-K问题就是求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都是比较大的。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于TOP-K问题，我们能够想到的最简单直接的方法就是进行排序。但是，如果数据量非常大时，排序的效率就会变得很低（可能出现数据不能一下全部加载到内存中的情况）。因此解决TOP-K问题的最佳方式是使用堆，基本思路如下：

（1）用数据集合中的前K个元素来建堆：

如果用前K个最大的元素，则建小堆；如果用前K个最小的元素，则建大堆。

（2）用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素：

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

要解决TOP-K问题，我们需要先利用C语言篇学到的文件操作的相关知识，来造一些数据：

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

这样我们就生成了100000个随机数，并把它们存储在了“data.txt”文件中。

下面我们就来正式尝试解决一下TOP-K问题：

2.1 实现逻辑

（1）获取用户输入K：通过scanf读取需要查找的前 K 个元素数量。

（2）文件操作初始化：打开数据文件data.txt，处理文件打开失败的异常。

（3）创建小堆：

动态分配大小为 K 的数组minHeap（用于存储候选的前 K 个最大元素）；
从文件中读取前 K 个数据存入数组；
通过AdjustDown将数组调整为小堆（堆顶为当前 K 个元素中的最小值）。

（4）筛选剩余数据：

遍历文件中剩余的所有数据；
若当前数据大于小堆的堆顶（说明该数据比当前候选的最小元素更大，有资格进入前 K），则替换堆顶并通过AdjustDown重新调整为小堆。

（5）输出结果：循环结束后，小堆中存储的就是整个文件中最大的前 K 个元素，打印输出。

（6）资源释放：关闭文件。

完整代码如下所示：

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);
	}
	//读取文件中k个数据放到数组中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//数组调整建堆--向下调整建堆
	//找最大的前K个数，建小堆
	for (int i = (k-1-1)/2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}
	//遍历剩下的n-k个数，跟堆顶比较，谁大谁入堆
	int data = 0;
	while (fscanf(fout,"%d",&data) != EOF)
	{
		if (data > minHeap[0])
		{
			minHeap[0] = data;
			AdjustDown(minHeap, 0, k);
		}
	}

	//打印堆里的数据
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");

	fclose(fout);
}

2.2 底层原理

2.2.1 为何使用小堆而非大堆？

我们的目标是找 “最大的前 K 个元素”，小堆的堆顶是当前候选集中的最小值。当新元素大于堆顶时，说明它比候选集中最小的元素更大，是有资格替换堆顶进入候选集的。

若使用大堆，堆顶是候选集中的最大值，是无法通过简单比较判断新元素是否应进入候选集的（新元素可能比堆顶小但比其他元素大）。

2.2.2 时间复杂度优化

在传统方法中，是对所有数据排序后取前 K 个，时间复杂度为（n 为数据总量）。

在堆解法中，建堆时间为，遍历剩余数据并调整堆的时间为，整体复杂度为。当 n 极大（如百万 / 亿级）且 K 较小时（如 100），性能优势是十分显著的。

2.2.3 空间复杂度优势

堆解法仅需要的空间存储小堆，适合处理无法一次性加载到内存的海量数据（如大文件）。

2.3 应用示例

假设data.txt中存储以下数据（共 10 个元素）：

5 9 3 12 7 15 2 8 11 6

当用户输入k=3时，期望输出最大的 3 个元素：15、12、11。

首先读取前 3 个数据[5, 9, 3]，建小堆后为[3, 9, 5]（堆顶 3 是当前最小值）

接着遍历剩余数据：

                12 > 3 → 替换堆顶为 12，调整后小堆为[5, 9, 12]；

                7 > 5 → 替换堆顶为 7，调整后小堆为[7, 9, 12]；

                15 > 7 → 替换堆顶为 15，调整后小堆为[9, 15, 12]；

                2 ≤ 9 → 不处理；

                8 ≤ 9 → 不处理；

                11 > 9 → 替换堆顶为 11，调整后小堆为[11, 15, 12]；

                6 ≤ 11 → 不处理。

最终小堆[11, 15, 12]中存储的就是最大的 3 个元素（输出顺序可能因堆结构而略有不同）。

2.4 执行流程

（1）输入与初始化：

用户输入 K 值（如 3）；
打开data.txt，分配大小为 K 的数组minHeap。

（2）构建初始小堆：

读取前 K 个数据到minHeap；
从最后一个非叶子节点(k-1-1)/2开始，通过AdjustDown将数组调整为小堆（确保堆顶是当前最小值）。

（3）筛选剩余数据：

循环读取文件中剩余的每个数据data：
- 若data > 堆顶（说明data比当前候选集中最小的元素大）：
  - 用data替换堆顶元素；
  - 调用AdjustDown从堆顶开始调整，维持小堆性质。
- 否则：跳过该数据。

（4）输出结果：

小堆中保存的 K 个元素即为整个文件中最大的前 K 个，打印输出。

最终我们可以得到TOP-K问题的时间复杂度为：。

数据结构（C语言篇）：（十三）堆的应用

目录

前言