【堆的应用】细说Top-K问题

大家好,这里是针对二叉树中顺序储存的堆结构的应用TOP-K问题，整理出来一篇博客供我们一起复习和学习,如果文章中有理解不当的地方,还希望朋友们在评论区指出,我们相互学习,共同进步! 文末附完整代码。

⭐️⭐️⭐️Top-K问题，也就是求众多数据中前K个最大的或者最小的元素，一般情况下数据量是很大的。
比如：求年级成绩前10名，游戏活跃榜度前100名等。
❗️❗️❗️对于TOP-K问题，最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存）。最佳的方式就是用堆来解决。
👉👉👉基本思路我们分两步：

1. 用数据集合中前K个元素来建堆
   1️⃣:求前K个最大的元素，则建小堆。
   2️⃣:求前K个最小的元素，则建大堆。
2. 用剩余的n - k 个元素依次与堆顶元素比较，若不满足则替换掉堆顶元素，再进行相应的调整。

将剩余的 n-k 个元素依次与堆顶元素比较完之后，堆中剩余的k个元素就是所求的前k个最小或者最大元素。

🙉：堆顶元素一定是堆中的最小元素（小顶堆为例）,若后面有大于堆顶的数据，理所当然与堆顶元素交换，交换之后再调整堆。循环往复堆中的元素就是前K个最大的元素。
👉对堆的调整算法不清楚的请点击这里

👇👇👇下面我们以求前K个最大的元素为例：
1️⃣:先备好所有数据：

void TestTopk()
{
	int n = 10000;
	vector<int> v;
	v.resize(10000, 0);
	srand((size_t)time(0));
	for (int i = 0; i < n; i++)
	{
		v[i] = rand() % 1000000;
	}
	v[5] = 1000000 + 1;
	v[20] = 1000000 + 2;
	v[200] = 1000000 + 3;
	v[444] = 1000000 + 4;
	v[115] = 1000000 + 5;
	v[9999] = 1000000 + 6;
	v[3123] = 1000000 + 7;
	v[5278] = 1000000 + 8;
	v[6666] = 1000000 + 9;
	v[7656] = 1000000 + 10;

	PrintTopK(v, 10);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2️⃣:对数组的前K个元素采用向下调整算法建小堆。

void AdjustDown(vector<int>& v, int k, int root)
{
	int parent = root;
	int child = 2 * parent + 1;//左孩子
	while (child < k)
	{
		//选出左右孩子最小的
		if (child + 1 < k && v[child] > v[child + 1])
		{
			child++;
		}

		if (v[child] < v[parent])
		{
			swap(v[child], v[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//1：用数组前K个元素来建小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(v, k, i);
}
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

3️⃣:用剩余的N-K个元素依次与堆顶元素比较，不满足就替换堆顶元素,并相应向下调整。

for (int j = k; j < v.size(); j++)
	{
		if (v[0] < v[j])
		{
			swap(v[0], v[j]);
			AdjustDown(v, k, 0);//把换进来的新元素看是否需要向下调整
		}
	}
1
2
3
4
5
6
7
8

剩余n-k个元素依次比较完以后，堆中剩余的K个元素就是所求的前K个最大的元素。

总结：我们建堆可以选择向下调整或者向上调整算法，但需要注意，若是求前K个最大的元素需要建立小堆，若是求前K个最小的元素需要建立大堆。后续依次与对堆顶元素比较交换后需要用到向下调整算法重新调整为小顶堆/大顶堆。

完整代码：

#include
#include
#include

using namespace std;

//向下调整算法建小堆
void AdjustDown(vector<int>& v, int k, int root)
{
	int parent = root;
	int child = 2 * parent + 1;//左孩子
	while (child < k)
	{
		//选出左右孩子最小的
		if (child + 1 < k && v[child] > v[child + 1])
		{
			child++;
		}

		if (v[child] < v[parent])
		{
			swap(v[child], v[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void PrintTopK(vector<int>& v, int k)
{
	//1：用数组前K个元素来建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(v, k, i);
	}
	//前K个数小堆已经建好
	//用剩余的N-K个元素依次与堆顶元素比较，不满足就替换堆顶元素,并相应向下调整
	//将剩余n-k个元素依次比较完以后，堆中剩余的K个元素就是所求的前K个最大或者最小的元素。
	for (int j = k; j < v.size(); j++)
	{
		if (v[0] < v[j])
		{
			swap(v[0], v[j]);
			AdjustDown(v, k, 0);//把换进来的新元素看是否需要向下调整
		}
	}

	for (int m = 0; m < k; m++)
	{
		cout << v[m] << " ";
	}
	cout << endl;
}
void TestTopk()
{
	int n = 10000;
	vector<int> v;
	v.resize(10000, 0);
	srand((size_t)time(0));
	for (int i = 0; i < n; i++)
	{
		v[i] = rand() % 1000000;
	}
	v[5] = 1000000 + 1;
	v[20] = 1000000 + 2;
	v[200] = 1000000 + 3;
	v[444] = 1000000 + 4;
	v[115] = 1000000 + 5;
	v[9999] = 1000000 + 6;
	v[3123] = 1000000 + 7;
	v[5278] = 1000000 + 8;
	v[6666] = 1000000 + 9;
	v[7656] = 1000000 + 10;

	PrintTopK(v, 10);
}


int main()
{
	TestTopk();
	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