100亿个数中找出最大的前K个数（海量TopK问题）

对于这个问题，可以有以下思考：
给了多少内存存储这100亿个数据？
先思考：堆排序效率是nlogn,再思考：可以将这些数据切成等份，再从每一份中找出最大前k个数据，但是效率不高。那如果利用堆的性质呢？
小堆堆顶元素最小，先将前k个数建成小堆，那么堆顶元素就是最小的，k+1的数依次与堆顶元素进行比较，如果大于，则K+1与堆顶元素交换，依次循环直至所有数据全部比较完，那么这个堆里存放的是最大的前K 个数。
代码如下：

void HeapInit(Heap* hp, HeapDatatype* a, int n)//堆的初始化
{
    assert(a&&hp);
    hp->capacity = n;
    hp->size = n;
    hp->arry = (HeapDatatype*)malloc(sizeof(HeapDatatype)*hp->capacity);
    int i = 0;
    for (i = 0; i < hp->size; i++)
        hp->arry[i] = a[i];
}
void SmallHeapMake(Heap* hp,int k)//小堆的创建
{
    int i = 0;//从大堆最后一个非叶子结点开始
    for (i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        SmallHeapAdjustDown(hp, i,k);
    }
}
void SmallHeapAdjustDown(Heap*hp, int parent, int k)//向下调成小堆
{
    int child = parent * 2 + 1;
    while (parent < k)
    {    //如果左孩子大于右孩子，将child等于右孩子，即child存左右孩子较小坐标
        if (child + 1 < hp->size && hp->arry[child] > hp->arry[child + 1])
            child = child + 1;
        if (child < k &&hp->arry[parent] > hp->arry[child])//根大于孩子
        {
            Swap(&hp->arry[parent], &hp->arry[child]);
            // 调整之后需要以child为跟再调整一次，因为调整后可能导致根小于左右孩子
            parent = child;
            child = parent * 2 + 1;
        }
        else  //说明根大于左右孩子或者child大于hp->size，退出循环
            break;
    }
}
void HeapFindTopK(Heap *hp, int k, int n)//找一组数据里最大的前K个数,利用堆
{
    SmallHeapMake(hp,k);//建成小堆
    for (int j = k; j < n; j++)
    {
        if (hp->arry[0] < hp->arry[j])
            Swap(&hp->arry[0], &hp->arry[j]);
        SmallHeapAdjustDown(hp,  0,k);//小堆向下调整
    }
}

如果不建堆，直接用数组存K个数呢？
代码如下：

void AdjustDown(int *a, int k, int root)//k个数据向下调整,没有建堆
{
    int parent = root;
    int child = parent * 2 + 1;
    if ((child+1)<k&&a[child] >a[child + 1])
        child++;
    while (child < k)
    {
        if (a[parent] >a[child])
        {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}
void FindTopK(int *a, int k, int n)//找一组数据里最大的前K个数
{    //没有建堆
    //先将前k个数调整成a[0]是最小数，k+1的数与a[0]元素进行比较，
    //如果大于，则交换，再将这K个数调整为a[0]最小，循环直至全部比较
    //那么数组里前k个数是最大的前k个数
    int i = 0;
    for (i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, k, i);//调整为a[0]最小
    }
    for (int j = k; j <n; j++)
    {
        if (a[j] > a[0])
            Swap(&a[j], &a[0]);
        AdjustDown(a, k, 0);
    }
}

Test函数：

void TestFindTopK()
{
    int a[] = {44 ,2 ,71 ,8,12,67,89};
    int i = 0;
    int k = 3;
    Heap hp;
    int size = sizeof(a) / sizeof(int);
    HeapInit(&hp, a, size);
    HeapFindTopK(&hp, k, size);
    for (i = 0; i < k; i++)
    {
        printf("%d ", hp.arry[i]);
    }
    printf("\n");
    FindTopK(a, k, size);//找出最大的前K个数
    for (i = 0; i < k; i++)
        printf("%d ", a[i]);
    printf("\n");
}

结果如下：