数据结构与算法_大数据处理_求topK的两种求解方法

这篇笔记记录求大数据topk的两种方法，分别是大小二叉堆法和快速分割法，下面依次详解这两种方法的过程。

1 大/小根堆法

利用大根堆过滤前top k小的数据**；小根堆过滤前top k大的数据**；
下面用大根堆求前k个小元素为例。

• 思想：
  把大根堆堆顶的大值不断的淘汰，放入小值。先构建k个元素的大小堆（比如k=3，就是求数列中前3个元素），然后用数列中的元素依次与堆顶元素比较，如果大于或者小于堆顶元素，就进行出堆调整；最后再进行入堆调整。
• 过程
  先用数列中前k个元素构建一个堆，比如构建一个大根堆。新元素与堆顶元素比较，大于堆顶元素就进行下一个元素；如果新元素比堆顶元素小，堆顶元素先出堆，然后将新元素加入到堆中。
  

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;

int main()
{
	vector<int> vec;
	srand(time(NULL));
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(rand() % 100);
		cout << vec[i] << " ";
	}
	cout << endl;
	// 求vec中值最小的前5个元素
	priority_queue<int> maxheap;
	int k = 5;

	// 前5个元素入堆
	for (int i = 0; i < 5; i++)
	{
		maxheap.push(vec[i]);
	}

	// 遍历剩余元素，直到最后
	for (int i = 5; i < vec.size(); i++)
	{
		if (maxheap.top() > vec[i])
		{
			maxheap.pop();
			maxheap.push(vec[i]);
		}
	}

	// 输出结果  
	while (!maxheap.empty())
	{
		cout << maxheap.top() << " ";
		maxheap.pop();
	}
	cout << endl;
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

求出序列中值最大的前k个元素

	priority_queue<int, vector<int>, greater<int>> minheap;
	// 前5个元素入堆
	for (int i = 0; i < 5; i++)
	{
		minheap.push(vec[i]);
	}
	
	// 遍历剩余元素，直到最后
	for (int i = 5; i < vec.size(); i++)
	{
		if (minheap.top() < vec[i])
		{
			minheap.pop();
			minheap.push(vec[i]);
		}
	}

	// 输出结果  
	while (!minheap.empty())
	{
		cout << minheap.top() << " ";
		minheap.pop();
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2 快排分割法

背景: 实际工作场景中经常遇到求topk的问题，比如找出最近人们搜索最多的商品，最多的应用等，多属于topk的问题，除了上面的利用大小根堆来求解topk问题之外，还可以利用快速排序思想求解topk问题。
**算法思想：**利用快速排序算法思想，判断快排分割函数每次返回的Pos值，如果pos值等于topk就直接返回，这样数组中从0到pos位置求出的就是前topk；如果pos大于或者小于topk，就继续求解。
算法步骤：
利用了快速排序的步骤。

算法性能分析：
平均时间复杂度：第一次找出一半的元素，第二次递归分割直达pos = K-1 ；一共N个元素，平均结果如下：
O(n)=N + N/2 +N/4 + … + 1 = 2N = O(n)
**最坏情况下时间复杂度：如果原始数列是有序的，比如从小到大的排列的，这时候求最大的top1时候，时间复杂度如下：
N +(N-1) + (N-2) +(N -3) + … + 1 = O(N^2)=**O(n2)

代码

#include 
#include 
#include 
using namespace std;


/*
* 功能：快排分割函数。每次递归时，将数组中的数据分割为两组，分别比val大的分成一组，比val小的分成一组。
*
* 参数：
*	arr[]: 要分割的数组
*	begin: 数组开始下标
*	end  : 数组的结束位置
*/		
int Partition(int arr[], int begin, int end)
{
	int val = arr[begin];
	int i = begin;
	int j = end;

	while (i < j)
	{
		while (i < j && arr[j] > val)
		{
			j--;
		}
		// 如果找到右边的值大于begin，就进行下面的操作，把比val大的放在
		if (i < j)
		{
			arr[i] = arr[j];
			i++;
		}

		while (i < j && arr[i] < val)
		{
			i++;
		}
		if (i < j)
		{
			arr[j] = arr[i];
			j--;
		}
	}

	arr[i] = val;
	return i;
}

/*
* 功能：求出前topk
*
* 参数：
*	*arr : 求topk的数组
*	begin: 数组开始下标
*	end  : 数组的结束位置
*	k    : 要求解的前topk。
*/
void SelectTopK(int *arr, int begin, int end ,int k)
{
	int pos = Partition(arr, begin, end);
	if (pos == k - 1) // 如果上面分割好的pos中间位置，刚好等于topk,直接返回。
	{				
		return;
	}
	else if (pos > k - 1)  // 假如返回 5  而要找topk=3,则继续快排分割。
	{
		SelectTopK(arr, begin, pos - 1, k);
	}
	else
	{
		SelectTopK(arr, begin, pos - 1, k);
	}
}
int main()
{

	int arr[] = { 64,45,52,80,66,68,0,2,18,75 };
	int size = sizeof arr / sizeof arr[0];

	// 假如求最小的topK，最后返回数组中的topk个元素。
	int k = 3;
	SelectTopK(arr, 0, size - 1,k);

	for (int i = 0; i < k; i++)
	{
		cout << arr[i] << " ";
	}

	cout << endl;
	system("pause");
	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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92