【海量数据处理】N个数中找出最大的前K个数-创新互联

N个数中找出大的前K个数，需要用小堆实现。

成都创新互联公司主要业务有网站营销策划、成都网站设计、成都网站建设、微信公众号开发、微信小程序、H5场景定制、程序开发等业务。一次合作终身朋友，是我们奉行的宗旨；我们不仅仅把客户当客户，还把客户视为我们的合作伙伴，在开展业务的过程中，公司还积累了丰富的行业经验、成都全网营销推广资源和合作伙伴关系资源，并逐渐建立起规范的客户服务和保障体系。 

分析：由于小堆的堆顶存放堆中最小的数据，可以通过与堆顶数据进行比较，将大数据存放在堆中，注意在每次改变堆顶数据后，进行调堆，使堆顶一直存放整个堆中最小元素。

void AdjustDown(int *a, size_t root, size_t size)//下调
{//小堆
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child] > a[child + 1])
		{
			++child;
		}
		if (a[parent] > a[child])
		{
			swap(a[parent], a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else//注意不满足交换条件时跳出本次循环
		{
			break;
		}
	}
void CreateRetPacket(vector<int>& moneys)//创建N个数
{
	srand((unsigned int)time(NULL));
	//srand(time(0));
	moneys.reserve(N);
	for (size_t i = 0; i<N; i++)
	{
		moneys.push_back(rand() % 1000);//产生N个随机值
	}
	for (size_t i = K; i < N; ++i)
	{
		moneys[i] *= 100;
	}
}
void GetTopk(const vector<int>& moneys, int n, int k)//N个数中找大的前k个数--小堆实现
{
	assert(n>k);
	int *TopkArray = new int[k];//通过前k个元素建立含有k个元素的堆
	for (size_t i = 0; i < k; i++)
	{
		TopkArray[i] = moneys[i];
	}
	for (int i = (k - 2) / 2; i >= 0; --i)//建小堆
	{
		AdjustDown(TopkArray, i, k);
	}
	//从第k个元素开始到第n个元素分别与堆顶元素进行比较，较大数据入堆顶，再对整个堆进行下调，使堆顶存放最小元素（小堆）
	for (size_t i = k; i < n; ++i)
	{
		if (moneys[i]  > TopkArray[0])
		{
			TopkArray[0] = moneys[i];
			AdjustDown(TopkArray, 0, k);
		}
	}
	size_t count = 0;
	for (size_t i = 0; i < k; ++i)//打印k个大数据，即堆中所有元素
	{
		cout << TopkArray[i] << " ";
		++count;
		if (count % 10 == 0)
		{
			cout << endl;
		}
	}
	cout << endl;
	delete[] TopkArray;//注意释放TopkArray所占的内存
	TopkArray = NULL;
}

测试用例如下：

#include<iostream>
#include<assert.h>
#include<vector>//容器--类模板
#include<stdlib.h>//利用随机值
#include<time.h>
using namespace std;

#define N 10000
#define K 100
void Test8()
{//N个里面找大的前k个数
	vector<int> moneys;
	CreateRetPacket(moneys);
	GetTopk(moneys, N, K);
}

上述可实现下列题：

    春节期间，A公司的支付软件某宝和T公司某信红包大乱战。春节后高峰以后，公司Leader要求后台的攻城狮对后台的海量数据进行分析。先要求分析出各地区发红包金额最多的前100用户。现在知道人数最多的s地区大约有1000w用户。

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

分享题目：【海量数据处理】N个数中找出最大的前K个数-创新互联
URL标题：https://www.cdcxhl.com/article18/dpcedp.html

成都网站建设公司_创新互联，为您提供ChatGPT、外贸网站建设、网站营销、定制开发、网页设计公司、服务器托管

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联