海量数据处理的 Top K算法(问题) 小顶堆实现解析

访客 阅读:387 2020-10-19 15:34:58 评论:0

  问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10)

  问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。

        可以利用数据结构的最小堆来处理该问题。

        最小堆如图所示,对于每个非叶子节点的数值,一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。

      每次有数据输入的时候可以先与根节点比较。若不大于根节点,则舍弃;否则用新数值替换根节点数值。并进行最小堆的调整。

  实现代码以及说明:

#include<stdio.h> 
int n;  ///数字个数,n很大(n>10000) 
int dui[10]; 
#define K 10    ///Top K,K的取值 
 
void create_dui();  ///建堆 
void UpToDown(int);  ///从上到下调整 
int main() 
{ 
    int i; 
    int tmp; 
    while(scanf("%d",&n)!=EOF) 
    { 
        for(i=1;i<=K;i++) ///先输入K个 
            scanf("%d",&dui[i]); 
        create_dui();  ///建小顶堆 
        for(i=K+1;i<=n;i++) 
        { 
            scanf("%d",&tmp); 
            if(tmp>dui[1])  ///只有大于根节点才处理 
            { 
                dui[1]=tmp; 
                UpToDown(1);    ///向下调整堆 
            } 
        } 
    } 
    return 1; 
} 
 
void create_dui() 
{ 
    int i; 
    int pos=K/2;      ///从末尾数,第一个非叶节点的位置K/2 
    for(i=pos;i>=1;i--) 
        UpToDown(i); 
} 
 
void UpToDown(int i) 
{ 
    int t1,t2,tmp,pos; 
    t1=2*i; ///左孩子(存在的话) 
    t2=t1+1;    ///右孩子(存在的话) 
    if(t1>K)    ///无孩子节点 
        return; 
    else 
    { 
        if(t2>K)  ///只有左孩子 
            pos=t1; 
        else 
            pos=dui[t1]>dui[t2]? t2:t1; 
 
        if(dui[i]>dui[pos]) ///pos保存在子孩子中,数值较小者的位置 
        { 
            tmp=dui[i];dui[i]=dui[pos];dui[pos]=tmp; 
            UpToDown(pos); 
        } 
    } 
}

   由于仅仅保存了K个数据,有调整最小堆的时间复杂度为O(lnK),因此TOp K算法(问题)时间复杂度为O(nlnK).

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
KIKK导航

KIKK导航

关注我们