海量数据处理的 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).

相关文章
|
1月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
67 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
6月前
|
存储 机器学习/深度学习 算法
数据结构与算法:堆
朋友们大家好啊,本篇文章来到堆的内容,堆是一种完全二叉树,再介绍堆之前,我们首先对树进行讲解
数据结构与算法:堆
|
3月前
|
存储 负载均衡 算法
从海量数据中挖出TOP100热词,这个算法太绝了!
小米,一位热爱技术的29岁程序员,今天探讨如何在海量搜索词汇中找出最热的TOP100词汇。面对包含数百亿词汇的大文件,小米介绍了一种实用的方法:通过哈希分流将大文件拆分成小文件,接着利用哈希表统计词频,并运用小根堆选出每个小文件的TOP100词汇。最后通过外排序或再次使用小根堆选出全局TOP100。此外还提出了并行处理、内存优化及数据压缩等优化手段。这一系列技巧能有效应对大数据处理挑战。
63 9
|
3月前
|
数据采集 算法
基于PSO粒子群算法的三角形采集堆轨道优化matlab仿真
该程序利用PSO算法优化5个4*20矩阵中的模块采集轨迹,确保采集的物品数量及元素含量符合要求。在MATLAB2022a上运行,通过迭代寻优,选择最佳模块组合并优化轨道,使采集效率、路径长度及时间等综合指标最优。具体算法实现了粒子状态更新、需求量差值评估及轨迹优化等功能,最终输出最优轨迹及其相关性能指标。
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
4月前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
39 0
|
4月前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
68 0
|
4月前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
50 0
|
5月前
|
存储 算法
【数据结构和算法】---二叉树(2)--堆的实现和应用
【数据结构和算法】---二叉树(2)--堆的实现和应用
24 0
|
6月前
|
存储 机器学习/深度学习 算法
数据结构与算法⑬(第四章_中_续二)堆解决Topk问题+堆的概念选择题
数据结构与算法⑬(第四章_中_续二)堆解决Topk问题+堆的概念选择题
55 3
下一篇
无影云桌面