C语言TopK问题

时间:2022-06-28 配的上了吗人气:0

问题

在一百万个数据中，求出最大的k个数字，怎么效率高。

1. 将一百万个数据排序，承接上一篇的堆排序，时间复杂度为O(N * LogN)。但是显然这并不是最优解。

2. 一百万个数据放入一个数组中，将其视为一个完全二叉树，并用向下调整算法将其调整为一个大堆/小堆，然后Top/Popk次，即可求出前K个最大/最小的数字，时间复杂度为：O（N + K*LogN）

3. 用正确的堆处理TopK算法：先假设求最大的K个数字，则建立大小为K的小根堆，然后在一百万-k个数据中，逐个遍历，若某个数据比小根堆的堆顶元素大，则替换掉堆顶元素，然后向下调整，使得这个堆重新变回一个小根堆。时间复杂度为:O(K + (N-k)*LogK)

其实相较于2，3并没有时间上的很大提升，但是3在空间复杂度上有了巨大提升，2的空间为O(N),3为O(K)。折中思考，3方法是求数据量较大的数据集合中前K个最大值/最小值的最佳方法

分析

求K个最大值，建小堆，是因为，若遍历途中遇到了那K个数中的某一个，他一定比堆顶元素大，然后替换进去之后，向下调整，可以使得这个数字置于这个小根堆的底部。从而达到目的。

代码实现

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			swap(a[parent], a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* a,int size, int parent) // size 是总大小，parent是从哪里开始向下调整 
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
			child++;
		if (a[child] > a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void Print_Heap_Topk(int* a, int n, int k)
{
	int* KMaxHeap = new int[k];   // 最大堆存最小的K个数
	for (int i = 0; i < k; ++i)
	{
		KMaxHeap[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(KMaxHeap, k, i);
	}
	for (int i = k; i < n; ++i)
	{
		if (a[i] < KMaxHeap[0])
			KMaxHeap[0] = a[i];
		AdjustDown(KMaxHeap, k, 0);
	}
	for (int i = 0; i < k; ++i)
	{
		cout << KMaxHeap[i] << " ";
	}
	cout << endl;
}
void test_topk()
{
	int n = 10000;
	int* a = new int[n];
	srand(time(0));
	for (int i = 0; i < n; ++i)
		a[i] = rand() % 1000000;
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[120] = 1000000 + 5;
	a[99] = 1000000 + 6;
	a[0] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	a[333] = -100;
	a[999] = -200;
	a[777] = -500;
	a[888] = -800;
	a[111] = -1000;
	a[798] = -1;
	a[1111] = -250;
	a[2222] = -350;
	a[3333] = -450;
	a[4444] = -550;
	Print_Heap_Topk(a, n, 10);
}
int main()
{
	test_topk();
	return 0;
}

加载全部内容