简单的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[0])return;
    int p = 0;
    int q = 0;
    h[0] = n;
    while(p < K)
    {
        q = 2*p +1;
        if (q >= K) break;
        if (h[p] < h[q] && h[p] < h[q+1])break;
        if (h[2*p+1] > h[2*p+2] ) q++;
        int tem = h[q];
        h[q] = h[p];
        h[p] = tem;
        p = q;

    }
}
本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/p/3952218.html ，如需转载请自行联系原作者
相关文章：
