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

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比莊浪網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式莊浪網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋莊浪地區(qū)。費(fèi)用合理售后完善，10年實(shí)體公司更值得信賴。

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

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//注意不滿足交換條件時跳出本次循環(huán)
		{
			break;
		}
	}
void CreateRetPacket(vector& moneys)//創(chuàng)建N個數(shù)
{
	srand((unsigned int)time(NULL));
	//srand(time(0));
	moneys.reserve(N);
	for (size_t i = 0; i& moneys, int n, int k)//N個數(shù)中找最大的前k個數(shù)--小堆實(shí)現(xiàn)
{
	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個元素分別與堆頂元素進(jìn)行比較，較大數(shù)據(jù)入堆頂，再對整個堆進(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個最大數(shù)據(jù)，即堆中所有元素
	{
		cout << TopkArray[i] << " ";
		++count;
		if (count % 10 == 0)
		{
			cout << endl;
		}
	}
	cout << endl;
	delete[] TopkArray;//注意釋放TopkArray所占的內(nèi)存
	TopkArray = NULL;
}

測試用例如下：

#include
#include
#include//容器--類模板
#include//利用隨機(jī)值
#include
using namespace std;

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

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

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