【海量數(shù)據(jù)處理】N個數(shù)中找出最大的前K個數(shù)
N個數(shù)中找出最大的前K個數(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ū)。費用合理售后完善，10年實體公司更值得信賴。
分析：由于小堆的堆頂存放堆中最小的數(shù)據(jù)，可以通過與堆頂數(shù)據(jù)進行比較，將大數(shù)據(jù)存放在堆中，注意在每次改變堆頂數(shù)據(jù)后，進行調(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ù)--小堆實現(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個元素分別與堆頂元素進行比較，較大數(shù)據(jù)入堆頂，再對整個堆進行下調(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 //利用隨機值 #include using namespace std; #define N 10000 #define K 100 void Test8() {//N個里面找最大的前k個數(shù) vector moneys; CreateRetPacket(moneys); GetTopk(moneys, N, K); }
上述可實現(xiàn)下列題：
春節(jié)期間，A公司的支付軟件某寶和T公司某信紅包大亂戰(zhàn)。春節(jié)后高峰以后，公司Leader要求后臺的攻城獅對后臺的海量數(shù)據(jù)進行分析。先要求分析出各地區(qū)發(fā)紅包金額最多的前100用戶?，F(xiàn)在知道人數(shù)最多的s地區(qū)大約有1000w用戶。
當前文章：【海量數(shù)據(jù)處理】N個數(shù)中找出最大的前K個數(shù)
文章分享：http://m.jiaotiyi.com/article/jpedoi.html