【算法篇】利用堆高效解决大数据量时TOP-K问题

堆相关博客： 堆

1.问题描述

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

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

2.分析问题

最简单的方法就是排序，先排好序再取前k个数。
或者建立一个堆，存放所有的数据元素，依次弹出堆顶元素即可
但是这两种方法在数据量非常大时是不可取的
如果我们要排的是一个文件中的数据，如果数据非常多的话，可能数据都不能一下子加载到内存当中，所以我们要换一种思路，能不能每次让加载到内存中的数据量少一点，但又不影响我们的最终的要求。

3.思路

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
   将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

我们要求前k个最大元素，就建小堆。
原因是：一开始把数据中前k个数放进了我们建的堆，我们把它建成小堆的话，最顶部的元素一定是这个堆里面最小的数，然后依次拿N-K个元素与堆顶比较，比堆顶元素大的数就进来，然后因为我们是小堆，所以这个数会向下调整，原来堆中第二小的数到顶部，然后继续拿数据与堆顶比较，满足条件就进来，进来后就调整，这样一直下去直到结束，就是前数据中前k个最大的元素。

要求前k个最小的元素，则建大堆，与上同理。

4.复杂度分析

1.时间复杂度 O(N * log₂K)

首先是选K个数放进堆，然后最坏情况下是每次都调整，就是(N-K)*log₂K
K + (N - K) * log₂K可以近似成 N * log₂K

2.空间复杂度O(K)

5.代码实现

我们的data.txt文件数据是

在这里我们给的数据量很小来测试。

#include 
void swap(int* n1, int* n2)
{
	int tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}
void down(data_type* a, int len, int parent) //向下调整
{
	int child = (parent * 2) + 1; // 先假设左孩子最大
	while (child < len)
	{
		//这里加1可能会有越界问题，可能会访问到随机值，导致出错,判断一下
		if (child + 1 < len && a[child + 1] < a[child]) // 如果右孩子大的话就 child++
		{
			child++;
		}
		if (a[parent] > a[child])//建立小根堆
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = (parent * 2) + 1;
		}
		else
		{
			break;
		}
	}
}
void test1()
{
	int minHeap[5];//建立一个堆，大小为5
	FILE* fout = fopen("data.txt", "r");//文件操作
	if (fout == NULL)//养成好习惯判断是否打开文件成功
	{
		perror("fopen");
		return;
	}
	int k = 5;//这里我们假设要求前5大的数
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);//先往堆里读入前K个数
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)//建堆算法，不了解的可以看看文章开头提到的博客
	{
		down(minHeap, k, i);//
	}
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)//继续读入N-K个数据，满足条件就进堆，进堆后进行调整。
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			down(minHeap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);//打印前5大的数
		//77 777 999 9999 10000
	}
	fclose(fout);//养成好习惯fclose()
}
int main()
{
	test1();
	return 0;
}
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
57
58
59
60
61
62
63
64
65
66
67
68

6.总结

这里的优化避免我们需要排序文件中的数据时，文件中的数据量如果过大，一下子不能加载进来的情况（因为文件在磁盘，而我们的数组元素在内存。比如文件中有100亿个整数，内存大小就是40G，非常大），所以我们一个一个读入，避免了这种情况的发生。