当前位置:   article > 正文

堆的应用--------Top-k问题(详解)_top k 最大的k个数 c++ 堆

top k 最大的k个数 c++ 堆

1.什么是Top-k问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

2.思路1—排序

这个方法很容易想到,用我们的堆排序解决的话,时间复杂度是O(nlogn).

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp;
	tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整
void ADjustDown(HPDataType* data, HPDataType father,int size)
{
	//法一:迭代
	//HPDataType child = father * 2 + 1;
	// //if ((data[child] < data[child + 1])&&(child+1<size))//找到孩子较大的一个
	//if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个

	//{
	//	child++;
	//}
	//while (child<size) 
	//{
	//	if (data[father] < data[child])//大堆
	//	//if (data[father] > data[child])//小堆
	// 
	//	{
	//		Swap(&data[father], &data[child]);
	//		father = child;//孩子变父亲,向下迭代
	//		child = father * 2 + 1;
	//	}
	//	else
	//	{
	//		break;
	//	}
	//}
	//法二:递归
	HPDataType child = father * 2 + 1;
	if (child >= size)return;
	else
	{
		//if ((data[child] < data[child + 1]) && (child + 1 < size))//大堆,找到孩子较大的一个
		if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个

		{
		child++;
		}
		//if (data[father] < data[child])//大堆
		if (data[father] > data[child])//小堆
		{
		Swap(&data[father], &data[child]);
		}
		ADjustDown(data,child,size);
	}
}	
void Heapsort(HPDataType* data,int size)
{
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		ADjustDown(data,i,size);
	}
	int end = size - 1;
	while (end > 0)
	{
		Swap(&data[0], &data[end]);
		ADjustDown(data, 0, end);
		end--;
	}
}
  • 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

3.思路2—建堆,Top/Pop k次

也就是说我们先建一个大堆(时间复杂度O(logn)),然后取出堆顶的元素,再删除,重复k次

for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		ADjustDown(data,i,size);
	}
	for(int i=0;i<k;i++)
	{
	printf("%d ",HeapTop(data);
	HeapPop(data);
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

4.思路3—建一个大小为k的小堆(最优解)

因为上述两种方法都是在内存中执行的,但是当我们 n很大时,占用内存很大,比如说n为100亿,
我们知道1G=1024MB=1024 * 1024KB==1024 * 1024 * 1024Byte约等于10亿Byte左右,就算有 那么大的内存,那么成本也很高!!!

所以我们采用建一个大小为k的小堆,为什么是小堆呢,我们知道小堆是用来排升序的,当我们向后遍历数据和堆顶比较,如果比堆顶大就替换,然后在向下调整,这样就大大减小内存的使用!!
但是用人会问,哪里一开始那个数据是n个那不也很大吗??对于这个问题的解释就是数据不一定是来自内存,可能来自硬盘,数据库,网络上的,而上述两种方法都是得存在内存上的,或者我们使用归并排序,但是数据不在内存上,归并排序效率会降低!!

代码:

//向下调整
void ADjustDown(HPDataType* data, HPDataType father,int size)
{
	//法一:迭代
	//HPDataType child = father * 2 + 1;
	// //if ((data[child] < data[child + 1])&&(child+1<size))//找到孩子较大的一个
	//if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个

	//{
	//	child++;
	//}
	//while (child<size) 
	//{
	//	if (data[father] < data[child])//大堆
	//	//if (data[father] > data[child])//小堆
	// 
	//	{
	//		Swap(&data[father], &data[child]);
	//		father = child;//孩子变父亲,向下迭代
	//		child = father * 2 + 1;
	//	}
	//	else
	//	{
	//		break;
	//	}
	//}
	//法二:递归
	HPDataType child = father * 2 + 1;
	if (child >= size)return;
	else
	{
		//if ((data[child] < data[child + 1]) && (child + 1 < size))//大堆,找到孩子较大的一个
		if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个

		{
		child++;
		}
		//if (data[father] < data[child])//大堆
		if (data[father] > data[child])//小堆
		{
		Swap(&data[father], &data[child]);
		}
		ADjustDown(data,child,size);
	}
}	
void PrintTopK(int* a, int n, int k)
{
	HPDataType* kMinHeap = (HPDataType*)malloc(sizeof(HPDataType) * k);
	assert(kMinHeap);
	for (int i = 0; i < k; i++)
	{
		kMinHeap[i] = a[i];
	}
	for (int i = (k-2)/2; i>=0; i--)
	{
		ADjustDown(kMinHeap, i,k );
	}
	for(int j=k;j<n;j++)
	{
		if (kMinHeap[0] < a[j])
		{
			kMinHeap[0] = a[j];
			ADjustDown(kMinHeap, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kMinHeap[i]);
	}
}
void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t 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[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/716783
推荐阅读
相关标签
  

闽ICP备14008679号