红包大乱战（海量数据处理）

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

问题分析：我们知道，对1000W个数据很难具体用一个排序来全部排出来所有元素，然后找出最大的100个。
所以想到最适合处理海量数据的堆来实现，现在用最大堆还是最小堆？我们会理所当然的想，要找最大的100个应该是用大堆。不过，堆是一个近似有序的序列，最大堆的特点是顶端元素为最大数，但不能保证最小元素会是哪个叶子结点，从而无法比较到底有没有比数列元素中最小的大的元素存在。所以我们要用最小堆。

具体实现方法如下：

// 创建红包数据
void CreateRedPacket(vector<int>& moneys)
{
    srand(time(0));
    moneys.reserve(N);
    for (int i = 0; i < N; ++i)
    {
        moneys.push_back(rand()%10000);
    }

    for(int j = N - K; j < N; ++j)
    {
        moneys[j] = rand() % N;
    }
}

void AdjustDown(int* a, size_t size, int root)
{
    int child = root*2+1;
    while (child < size)
    {
        if (child+1 <size && a[child+1] < a[child])
        {
            ++child;
        }

        if (a[child] < a[root])
        {
            swap(a[child], a[root]);
            root = child;
            child = 2*root+1;
        }
        else
        {
            break;
        }
    }
}

void GetTopK(vector<int>& moneys)
{
    int arrays[K] = {};
    for (size_t i = 0; i < K; ++i)
    {
        arrays[i] = moneys[i];
    }

    // 建小堆
    for(int i = (K-2)/2; i >= 0; --i)
    {
        AdjustDown(arrays, K, i);
    }

    for (size_t i = K; i < N; ++i)
    {
        if (arrays[0] < moneys[i])
        {
            arrays[0] = moneys[i];
            AdjustDown(arrays, K, 0);
        }
    }

    for (int i = 0; i < K; ++i)
    {
        cout<<arrays[i]<<" ";
    }

    cout<<endl;
}

void TestTopK()
{
    vector<int> moneys;
    CreateRedPacket(moneys);
    GetTopK(moneys);
}