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

分析：海量数据topK问题，在我们日常生活中应用非常广泛，比如微信的计步软件，它就是topK问题，统计出前K名，然后进行排序。那如何解决这个问题呢？我们用堆可以很好的解决这个问题。我们先用前K个数建立一个大堆/小堆（找最大前K个数用小堆，找最小前K个数用大堆，因为：如果找最大前K个数，我们建立一个大堆的话，我们需要用第N-K-1个数与堆顶元素比较，如果它比堆顶元素小我们就要舍弃它，但如果它比堆顶元素小，但比堆中其中一个元素大，我们把它舍弃的话，这样就会排序错误，不能达到目的，但如果我们建立的是小堆的话，堆顶元素是目前堆中最小的元素，如果一个数比堆中最小元素都小的话，那它比这个堆中任一元素都小，舍弃它；找最小的前K个数，建立最大堆也是这个道理），用剩余的N-K个数一一与堆顶也是比较，要么舍弃，要么与堆顶也是交换，再调整堆。
在这里的代码，会用到堆的调整和创建操作，在我们上一篇博客中我有写到，在这里我就直接调用了，如果不懂是话，可以点击这个链接，去看看堆调整和创建堆的代码：https://mp.csdn.net/mdeditor/82346337
代码：
topK.h

#ifndef __TOPK_H__
#define __TOPK_H__

#include"Heap.h"

typedef struct topK
{
    Heap hp;
}topK;

void CreatetopK(topK* t, HPDataType* array, int k, int size);

#endif //__TOPK_H__

topK.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"topK.h"


void CreatetopK(topK* t, HPDataType* array, int k, int size)
{
    assert(t);
    //用前K个元素建立一个小堆
    CreateHeap(&(t->hp), array, k, Less);
    //用剩余的N-K个元素与堆顶元素比较，若比堆顶元素大，与堆顶元素交换，调整，若比堆顶元素小，则舍弃该元素

    while (k < size)
    {

        int root = (k - 1) >> 1;
        if (t->hp._hp[0] < array[k])
        {
            Swap(&(t->hp._hp[0]), &(array[k]));
            AdjustDown(&(t->hp), root, Less);
            k += 1;
        }
        else
            k += 1;
    }
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"topK.h"

int main()
{
    topK t;
    HPDataType array[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
    int k = 5;
    CreatetopK(&t, array, k, 9);
    Print((t.hp));
    return 0;
}