建堆算法以及TopK算法分析-EW帮帮网

1 建堆算法

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：

1.1 向下调整

从倒数的第一个非叶子节点开始调。（最后一个叶子的父亲节点开始调）

得到规律如下：

所以：

需要移动节点总的移动步数为：

其中：

1两边同时乘2，可以得到2 式：

两式形成错位：

2式错位相减1式：

对H不是特别敏感。上述的TN和TH是一样的。

又因为：

所以：

H向N换。

N远大于logN

1.2 向上调整

从第二层开始，得到以下规律：

所以：

求和：

则：

2 TOP-K问题

Top-K 问题是数据处理中非常常见的场景，核心是从大量数据中快速找到前 K 个最大（或最小）的元素。由于数据量通常极大（如千万级、亿级），直接排序的效率极低，而堆（Heap） 是解决这类问题的最优方案。

1.1 为什么不直接用排序？

假设：

所以，由上可得：

排序是最直观的思路：对所有数据排序后，取前 K 个元素即可。但它有两个致命缺陷：

时间复杂度高：排序的时间复杂度为O(N log N)（N 为数据总量），当 N 极大（如 1 亿）时，计算成本极高；
内存限制：若数据无法一次性加载到内存（如 TB 级数据），排序（尤其是内部排序）根本无法执行，即使外部排序也效率低下。

2.2 堆解法的核心思路

堆的本质是一种 “优先级队列”，能高效维护一组元素中的最值。解决 Top-K 问题时，堆的核心作用是用一个大小为 K 的 “候选池” 过滤数据，只保留可能成为 Top-K 的元素，从而降低时间和空间成本。

具体逻辑根据 “求最大” 还是 “求最小” 略有不同，核心原则是：

求前 K 个最大元素：用小根堆（堆顶是当前候选池中最小的元素）；
求前 K 个最小元素：用大根堆（堆顶是当前候选池中最大的元素）。

2.3 分步解析：以 “前 K 个最大元素” 为例

假设要从 N 个数据中找到前 K 个最大的元素，步骤如下：

1. 用前 K 个元素建小根堆

小根堆的特性是：堆顶元素是堆中最小的元素。

选择前 K 个元素构建小根堆后，堆顶就是这 K 个元素中最小的一个。
此时，堆中的 K 个元素是 “当前候选的前 K 个最大元素”，而堆顶是这 K 个元素的 “门槛”—— 只有比它大的元素才有可能进入候选池。

2. 遍历剩余元素，过滤并更新堆

对剩下的（N-K）个元素，逐个与堆顶元素比较：

若当前元素 ≤ 堆顶：说明它不可能是前 K 个最大元素（连候选池的 “门槛” 都达不到），直接丢弃；
若当前元素 > 堆顶：说明它比候选池中最小的元素还大，有资格进入候选池。此时用它替换堆顶，然后重新调整堆结构（“向下调整”），使堆再次成为小根堆（保证新堆顶仍是当前候选池中的最小元素）。

3. 遍历结束后，堆中元素即为结果

当所有元素遍历完成后，小根堆中保留的 K 个元素就是整个数据集中前 K 个最大的元素。

原因：所有比堆顶小的元素都被过滤掉了，剩下的元素都 ≥ 堆顶（而堆顶是这 K 个元素中最小的），因此整体就是前 K 个最大元素。

2.4 举例说明

假设数据为 [3, 2, 1, 5, 6, 4]，求前 2 个最大的元素（K=2）。

步骤 1：用前 2 个元素建小根堆

前 2 个元素是 [3, 2]，构建小根堆后：

堆结构为 [2, 3]（堆顶是 2，即当前候选池中最小的元素）。

步骤 2：遍历剩余元素 [1, 5, 6, 4]

元素 1：1 ≤ 堆顶 2 → 丢弃；
元素 5：5 > 堆顶 2 → 替换堆顶为 5，调整小根堆。调整后堆为 [3, 5]（堆顶 3，仍是当前候选池最小元素）；
元素 6：6 > 堆顶 3 → 替换堆顶为 6，调整小根堆。调整后堆为 [5, 6]（堆顶 5）；
元素 4：4 ≤ 堆顶 5 → 丢弃。

步骤 3：结果

堆中元素为 [5, 6]，即前 2 个最大元素，正确。

2.5 求 “前 K 个最小元素” 的逻辑（对称）

与求最大元素对称，核心用大根堆（堆顶是当前候选池中最大的元素）：

用前 K 个元素建大根堆（堆顶是这 K 个元素中最大的）；
遍历剩余元素，若当前元素 < 堆顶 → 替换堆顶并调整大根堆（保证堆顶仍是候选池最大元素）；
遍历结束后，堆中元素即为前 K 个最小元素。

2.6 堆解法的优势

时间效率高
- 建堆时间：O (K)（堆的构建时间为 O (n)，n=K）；
- 遍历调整时间：O ((N-K) log K)（每个元素调整堆的时间为 O (log K)）；
- 总时间：O(N log K)，远优于排序的 O (N log N)（尤其当 K 远小于 N 时，如 K=100，N=1 亿，log K≈7，log N≈27）。
内存友好
只需维护大小为 K 的堆，无需加载全部数据到内存，适合流式处理或大数据场景（如处理 TB 级日志文件）。

2.7 对比其他方法

快速选择算法（基于快排思想）：平均时间 O (N)，但最坏 O (N²)，且依赖随机访问，不适合无法全量加载的大数据；
哈希表：仅适合去重场景，无法直接解决 Top-K；
堆解法：综合效率最高，尤其适合大数据和流式场景。

所以，Top-K 问题的最优解是用堆：求最大用小堆，求最小用大堆。核心逻辑是用大小为 K 的堆作为 “筛选器”，通过堆顶的 “门槛作用” 过滤无效元素，最终高效保留目标结果。这种方法在时间、空间上均优于排序，是大数据场景的首选。

2.8 实践一下

造数据：

#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
#include<time.h>

//造数据
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) % 10000000;
		//读写整数
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

创造数据完成：

检查一下数据：

TOPK的实现：

//TOPK
void TestHeap3()
{
	int k;
	printf("请输入k>:");
	scanf("%d", &k);

	//扩容
	int* kminheap = (int*)malloc(sizeof(int) * k);

	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	//打开文件，读文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	// 读取文件中前k个数
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	// 建K个数的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	// 读取剩下的N-K个数
	int x = 0;
	while (fscanf(fout, "%d", &x) > 0)
	{
		if (x > kminheap[0])
		{
			kminheap[0] = x;
			AdjustDown(kminheap, k, 0);
		}
	}

	printf("最大前%d个数：", k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}

int main()
{
	//TestHeap1();
	//TestHeap2();
	//CreateNDate();
	TestHeap3();

	return 0;
}

建堆算法以及TopK算法分析