【海量數(shù)據(jù)處理】N個(gè)數(shù)中找出最大的前K個(gè)數(shù)-創(chuàng)新互聯(lián)

N個(gè)數(shù)中找出大的前K個(gè)數(shù)，需要用小堆實(shí)現(xiàn)。

成都創(chuàng)新互聯(lián)公司主要業(yè)務(wù)有網(wǎng)站營(yíng)銷(xiāo)策劃、成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、微信公眾號(hào)開(kāi)發(fā)、微信小程序、H5場(chǎng)景定制、程序開(kāi)發(fā)等業(yè)務(wù)。一次合作終身朋友，是我們奉行的宗旨；我們不僅僅把客戶當(dāng)客戶，還把客戶視為我們的合作伙伴，在開(kāi)展業(yè)務(wù)的過(guò)程中，公司還積累了豐富的行業(yè)經(jīng)驗(yàn)、成都全網(wǎng)營(yíng)銷(xiāo)推廣資源和合作伙伴關(guān)系資源，并逐漸建立起規(guī)范的客戶服務(wù)和保障體系。 

分析：由于小堆的堆頂存放堆中最小的數(shù)據(jù)，可以通過(guò)與堆頂數(shù)據(jù)進(jìn)行比較，將大數(shù)據(jù)存放在堆中，注意在每次改變堆頂數(shù)據(jù)后，進(jìn)行調(diào)堆，使堆頂一直存放整個(gè)堆中最小元素。

void AdjustDown(int *a, size_t root, size_t size)//下調(diào)
{//小堆
	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//注意不滿足交換條件時(shí)跳出本次循環(huán)
		{
			break;
		}
	}
void CreateRetPacket(vector<int>& moneys)//創(chuàng)建N個(gè)數(shù)
{
	srand((unsigned int)time(NULL));
	//srand(time(0));
	moneys.reserve(N);
	for (size_t i = 0; i<N; i++)
	{
		moneys.push_back(rand() % 1000);//產(chǎn)生N個(gè)隨機(jī)值
	}
	for (size_t i = K; i < N; ++i)
	{
		moneys[i] *= 100;
	}
}
void GetTopk(const vector<int>& moneys, int n, int k)//N個(gè)數(shù)中找大的前k個(gè)數(shù)--小堆實(shí)現(xiàn)
{
	assert(n>k);
	int *TopkArray = new int[k];//通過(guò)前k個(gè)元素建立含有k個(gè)元素的堆
	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個(gè)元素開(kāi)始到第n個(gè)元素分別與堆頂元素進(jìn)行比較，較大數(shù)據(jù)入堆頂，再對(duì)整個(gè)堆進(jìn)行下調(diào)，使堆頂存放最小元素（小堆）
	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個(gè)大數(shù)據(jù)，即堆中所有元素
	{
		cout << TopkArray[i] << " ";
		++count;
		if (count % 10 == 0)
		{
			cout << endl;
		}
	}
	cout << endl;
	delete[] TopkArray;//注意釋放TopkArray所占的內(nèi)存
	TopkArray = NULL;
}

測(cè)試用例如下：

#include<iostream>
#include<assert.h>
#include<vector>//容器--類(lèi)模板
#include<stdlib.h>//利用隨機(jī)值
#include<time.h>
using namespace std;

#define N 10000
#define K 100
void Test8()
{//N個(gè)里面找大的前k個(gè)數(shù)
	vector<int> moneys;
	CreateRetPacket(moneys);
	GetTopk(moneys, N, K);
}

上述可實(shí)現(xiàn)下列題：

    春節(jié)期間，A公司的支付軟件某寶和T公司某信紅包大亂戰(zhàn)。春節(jié)后高峰以后，公司Leader要求后臺(tái)的攻城獅對(duì)后臺(tái)的海量數(shù)據(jù)進(jìn)行分析。先要求分析出各地區(qū)發(fā)紅包金額最多的前100用戶?，F(xiàn)在知道人數(shù)最多的s地區(qū)大約有1000w用戶。

創(chuàng)新互聯(lián)www.cdcxhl.cn，專(zhuān)業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買(mǎi)多久送多久。

分享題目：【海量數(shù)據(jù)處理】N個(gè)數(shù)中找出最大的前K個(gè)數(shù)-創(chuàng)新互聯(lián)
URL標(biāo)題：http://muchs.cn/article18/dpcedp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站營(yíng)銷(xiāo)、定制開(kāi)發(fā)、網(wǎng)頁(yè)設(shè)計(jì)公司、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

微信小程序開(kāi)發(fā)