简单的topK问题

/************************************************************************/

/*

求一组数据中的top（K）问题，这是一个经典的top（K）问题。

分析：

方法一：如果数据量不大，那么最常用的方法就是排序从大大小，然后找出前k个数据。

比较高效率的排序算法，如快排，堆排序等，总体时间复杂度为 O(N*log2(N))+O(K)=O(N*log2(N))

或是直接用部分排序算法，如选择排序，直接找出前K个元素，时间复杂度为O(N*K),

至于O(N*log2(N)) 还是O(N*K)效率高，看K的取值，若K<log2(N)那么部分排序效率高。

方法二：

如果数据量非常大，不能够加载到内存中，这就成了一个海量数据问题。求其中的top(K)

就是我们所求的前K个大的数据。

这样考虑，我们用一个长度为K大小的数组存储前k个数据，然后经过一次扫描数据，每次

扫描一个数据，和数据中最小的数据比较，如果小于这个数据，继续下一个数据扫描，如果

大于这个数据，那么就替换掉数组中最小的那个数据。这样所消耗的时间效率为O(N*K)

进一步，我们可以用容量为K大小的最小堆来存储前K个数据，如果我们新扫描的数据小于堆顶

的数据，那么我们就替换最小堆的堆顶数据，调整最小堆形成新的最小堆。

最小堆可以用一个长为K大小的数组h模拟，对于结点h[i]，其中父节点为h[i/2],

儿子节点为：h[2*i+1]和h[2*i+2];

*/

/************************************************************************/

/*

n为要判断的数字，h为最小堆，k为topk 即最小堆维持的大小。

*/

void topK(int n,int *h,int K)

{

    if(n<h[])return;

    int p = ;

    int q = ;

    h[] = n;

    while(p < K)

    {

        q = *p +;

        if (q >= K) break;

        if (h[p] < h[q] && h[p] < h[q+])break;

        if (h[*p+] > h[*p+] ) q++;

        int tem = h[q];

        h[q] = h[p];

        h[p] = tem;

        p = q;

    }

}