【海量数据处理】N个数中找出最大的前K个数-白红宇

【海量数据处理】N个数中找出最大的前K个数

阅读量：4030 次

发布时间：2019-05-24

本文共 1732 字，大约阅读时间需要 5 分钟。

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

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

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
   
    & moneys)//创建N个数{	srand((unsigned int)time(NULL));	//srand(time(0));	moneys.reserve(N);	for (size_t i = 0; i

& 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
   
    #include
    
     #include
     
      //容器--类模板#include
      
       //利用随机值#include
       
        using namespace std;#define N 10000#define K 100void Test8(){//N个里面找最大的前k个数	vector
        
          moneys; CreateRetPacket(moneys); GetTopk(moneys, N, K);}

上述可实现下列题：

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

本文出自 “” 博客，请务必保留此出处

转载地址：http://milbi.baihongyu.com/

你可能感兴趣的文章