海量数据处理的 Top K算法(问题) 小顶堆实现-阿里云开发者社区

开发者社区> 旭东的博客> 正文

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

简介:   问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10)   问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。
+关注继续查看

  问题描述:有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).

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
双11核心系统100%上云 !阿里数据库处理峰值远超传统厂商
刚刚结束的天猫双11创下了两项新记录:交易额2684亿,订单峰值54.4万笔/秒,阿里巴巴集团CTO张建锋在当晚宣布,双11核心系统100%上云,背后作为数据核心支撑的自研数据库OceanBase和POLARDB每秒处理峰值都远远超越传统Oracle数据库。
952 0
asp.net发布到IIS中出现错误:处理程序“PageHandlerFactory-Integrated”在其模块列表中有一个错误模块“ManagedPipelineHandler”
开发web项目时需要安装IIS,在安装好IIS的Windows7本上发布asp.net网站时,web程序已经映射到了本地IIS上,但运行如下错误提示“处理程序“PageHandlerFactory-Integrated”在其模块列表中有一个错误模块“Man...
822 0
SAP LSMW 导入OPEN PO 单据时候’税码’字段的处理
SAP LSMW Standard Batch (Direct) Input 方式制作的LSMW工具导入OPEN PO 单据时候’税码’字段的处理 如下的Open PO 批量导入LSMW工具,   ...
1087 0
能源物联网中如何处理上报的大量数据问题的思路分析(题目有点长,但是我不介意它更长)--后续会继续补充
V1.0       今年年底,随着运营的新能源车的增多,车辆上报上来的各种can消息也飞速增长,传统的关系型数据库已经无法满足存储的需要,因为转而向非关系型数据库去寻求帮助。目前面临的问题:         1,数据存储:large,粗略估计,明年预计每日过4亿;         2,c...
880 0
Spring-Aop处理记录日志
AOP的几种通知类型: 1,前置通知(Before advice):在某连接点(JoinPoint)之前执行的通知,但这个通知不能阻止连接点前的执行 配置文件中使用 &lt;aop:before&gt;进行声明 注解使用 @Before 进行声明 2,后置通知(After advice):当某连接点退出的时候执行的通知(不论是正常返回还是异常退出)。
2485 0
关于猫和老鼠的算法
做梦梦出来的题,自己都想不出来怎么解。http://www.cnblogs.com/aowind/archive/2005/03/07/114175.html请高手们给个算法吧!
593 0
+关注
旭东的博客
从事互联网开发工作,写博客,记录问题与学习支持,并分析
194
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载