亲宝软件园·资讯

展开

C语言TopK问题

配的上了吗 人气: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;
}

加载全部内容

相关教程
猜你喜欢
用户评论