【数据结构】TOP-K问题/使用堆解决

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
📆 个人专栏： 🔹数据结构与算法🔹C语言进阶
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

TOP-K问题

一、题目描述

假设有一亿个数据，内存存储不下，而我们只需要这一亿个数据中最大的前K个。

二、 思路：

1.：存前K个数据入堆
从第二个开始，每存储一个数据进来，就对其进行向上调整，使其一直保持为小堆。直到k-1个节点停止存储。
2.再从第K+1个数据开始读取
此时读取的数据就不再往堆中插入了，而是与堆顶元素进行比较，如果比堆顶大，那么就替换堆顶元素，然后进行基于小堆的向下调整。
3.所有数据读取完毕，堆中剩余的K个就是最大的K个数据

三、代码实现

1.随机产生一万个数据，存入文件中。

void CreateNDate()
{
	// 造数据
	int n = 10000000;
	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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.找前K个最大值

void PrintTopK(const char* filename, int k)
{
 建堆/用a中前k个元素建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
开辟K个元素空间
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}
将前k个元素读入数组minheap
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
 用前k个数建小堆，使用从下到上的向下调整方法建堆。
k-1下标的双亲节点是（k-1-1）/2；
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(minheap, k, i);
	}


将剩余n-k个元素依次与堆顶元素交换，不满足，则替换
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
替换堆顶元素进堆
			minheap[0] = x;
并且进行调整
			AdjustDown(minheap, k, 0);
		}
	}

遍历完所有n个数据后，打印出堆中的数据，就是最大的K个数据啦！
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	fclose(fout);
}

// fprintf  fscanf



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

3.测试类：

int main()
{
	//CreateNDate();
	PrintTopK("data.txt", 5);

	return 0;
}
1
2
3
4
5
6
7

四、时间复杂度和空间复杂度分析

🔸时间复杂度：O(N*logK);
N:节点个数。K：最大的前K个个数
如果N>>K，那么可以认为时间复杂度是O(N);这也是此算法的厉害之处。
🔸空间复杂度：O(K);
K：最大的前K个个数.