社区首页 >专栏 >【初探数据结构】堆的应用实例（堆排序与TopK问题）

【初探数据结构】堆的应用实例（堆排序与TopK问题）

我想吃余

发布于 2025-03-31 10:20:31

17800

代码可运行

文章被收录于专栏：数据结构初阶数据结构初阶 C语言学习

运行总次数：0

代码可运行

一、引言

堆是一种高效处理优先级问题的数据结构，尤其在动态数据流和排序场景中表现优异。本文将通过堆排序和TopK问题两个经典案例，深入解析堆的实际应用，并提供清晰的代码实现与原理分析。

二、堆排序：将无序数组变为有序序列

1. 堆排序的核心思想

利用最大堆的性质：堆顶元素始终为最大值。
两步走策略：
1. 建堆
- 升序：建大堆
- 降序：建小堆
1. 利用堆删除思想来进行排序
- 逐次提取堆顶：将堆顶元素（最大值）与数组末尾交换，缩小堆范围，重新调整堆。

2. 详细步骤图解（以升序排序为例）

初始数组：[4, 10, 3, 5, 1]

构建最大堆：
- 从最后一个非叶子节点（索引5//2 -1 =1）开始调整。
- 调整后得到最大堆：[10, 5, 3, 4, 1]。

💡 建堆的两种方式

向上调整建堆法: 时间复杂度O(nlogn),效率低，不推荐
向下调整建堆法用向下调整建堆时间复杂度O(n),推荐

//建大堆
	//1.用向上调整建堆  时间复杂度O(nlogn),效率低，不推荐
	for (i = 0; i < n; i++) {
		AdjustUp(a, i);
	}
	//2.用向下调整建堆  时间复杂度O(n),推荐
	for (i = (n - 1 - 1)/2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}

这里调整算法不再赘述。如有疑问，请学习“堆的实现” 或者与我交流哦😀

交换与调整：
- 交换堆顶10与末尾1 → 数组变为[1,5,3,4,10]，有效堆范围减1。
- 重新调整剩余元素[1,5,3,4]为最大堆 → [5,4,3,1]。
- 重复上述步骤，最终得到有序数组[1,3,4,5,10]。

3. 代码实现

//升序排序，用大根堆；
//降序排序，用小根堆。
void HeapSort(HPDataType* a,int n)
{
	//排升序
	int i = 0;

	//建大堆
	//1.用向上调整建堆  时间复杂度O(nlogn),效率低，不推荐
	/*for (i = 0; i < n; i++) {
		AdjustUp(a, i);
	}*/
	//2.用向下调整建堆  时间复杂度O(n),推荐
	for (i = (n - 1 - 1)/2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}

	//排序
	int end = n - 1;
	while (end > 0) {
		swap(a, &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
}

4. 时间复杂度与特点

时间复杂度：O(n log n)（构建堆O(n) + 每次调整O(log n)）。
原地排序：无需额外空间，适合内存敏感场景。
不稳定性：相同元素可能交换顺序。

三、TopK问题：海量数据中的高效筛选

1. 问题场景

需求：从一亿个数中快速找到前100大的数。
挑战：直接排序时间复杂度O(n log n)，内存可能无法容纳全部数据。

2. 堆的解决方案

最小堆策略（找最大的K个元素）：
1. 初始化：用前K个元素构建一个最小堆（堆顶为当前最小值）。
2. 遍历剩余元素：若当前元素 > 堆顶，则替换堆顶并调整堆。
3. 最终结果：堆中保留的K个元素即为TopK。
为什么用最小堆？
- 堆顶是K个元素中的最小值，遇到更大的值时替换，确保堆中始终保留更大的候选。

3.如何创建这么多数？

随机数生成：利用rand生成随机数
写入文件

void CreateNumber()
{
	int n = 10000;
	//时间种子
	srand((unsigned int)time(0));
	const char* file = "data.text";
	FILE* fp = fopen(file, "w");
	if (fp == NULL) {
		perror("fopen fail");
		return;
	}
	//写入文件
	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 10000;
		fprintf(fp, "%d\n", x);
	}
	fclose(fp);
	fp = NULL;
}

3. 代码实现

void PrintTopK(const char* file, int k)
{
	int* topk = (int*)malloc(sizeof(int) * k);
	if (topk == NULL) {
		perror("fopen fail");
		return;
	}
	FILE* fp = fopen(file, "r");
	if (fp == NULL) {
		perror("fopen fail");
		return;
	}
	//建前k个数的小根堆
	for (int i = 0; i < k; i++) {
		fscanf(fp,"%d",&topk[i]);
	}
	for (int i = (k - 2) / 2; i >= 0; i--) {
		AdjustDown(topk, k, i);
	}
	//遍历后面的数，若比堆top大，就覆盖并向下调整
	int val = 0;
	int ret = fscanf(fp, "%d", &val);
	while (ret != EOF) {
		if (val > topk[0]) {
			topk[0] = val;
			AdjustDown(topk, k, 0);
		}
		ret = fscanf(fp, "%d", &val);
	}
	for (int i = 0; i < k; i++) {
		printf("%d ", topk[i]);
	}
	free(topk);
	fclose(fp);
	fp = NULL;
}

4. 时间复杂度与优化

时间复杂度：O(n log K)，远优于O(n log n)。
处理数据流：逐个读取数据，内存仅需维护大小为K的堆。

四、对比与总结

应用场景	核心思路	时间复杂度	空间复杂度	优势
堆排序	构建堆 + 交换堆顶	O(n log n)	O(1)	原地排序，适合内存敏感
TopK问题	维护大小为K的最小堆	O(n log K)	O(K)	高效处理海量数据或数据流