专栏首页爱编码10亿个数字里里面找最小的10个

10亿个数字里里面找最小的10个

什么是TOP K问题

Top K指的是从n(很大)个数据中,选取最大(小)的k个数据。例如学校要从全校学生中找到成绩最高的500名学生,再例如某搜索引擎要统计每天的100条搜索次数最多的关键词。

对于这种问题,效率比较高的解决方法是使用最小堆。

什么是最大(小)堆

最大堆,最小堆类似,以下以最小堆为例进行讲解。

最小堆是满足以下条件的数据结构:

1)它是一棵完全二叉树

2)所有父节点的值小于或等于两个子节点的值。

最小堆:

最大堆:

什么是完全二叉树

除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐。

堆排序解决TOP K

对于TOPK问题,解决方法有很多:

方法一:对源数据中所有数据进行排序,取出前K个数据,就是TopK。

但是当数据量很大时,只需要k个最大的数,整体排序很耗时,效率不高。

方法二:维护一个K长度的数组a[],先读取源数据中的前K个放入数组,对该数组进行升序排序,再依次读取源数据第K个以后的数据,和数组中最小的元素(a[0])比较,如果小于a[0]直接pass,大于的话,就丢弃最小的元素a[0],利用二分法找到其位置,然后该位置前的数组元素整体向前移位,直到源数据读取结束。

这比方法一效率会有很大的提高,但是当K的值较大的时候,长度为K的数据整体移位,也是非常耗时的。

最小堆思路

最小堆(小根堆)是一种数据结构,它首先是一棵完全二叉树,并且,它所有父节点的值小于或等于两个子节点的值。

最小堆的存储结构(物理结构)实际上是一个数组。如下图:

堆有几个重要操作:

BuildHeap:将普通数组转换成堆,转换完成后,数组就符合堆的特性:所有父节点的值小于或等于两个子节点的值。

Heapify(int i):当元素i的左右子树都是小根堆时,通过Heapify让i元素下降到适当的位置,以符合堆的性质。

回到上面的取TopK问题上,用最小堆的解决方法就是:先去源数据中的K个元素放到一个长度为K的数组中去,再把数组转换成最小堆。再依次取源数据中的K个之后的数据和堆的根节点(数组的第一个元素)比较,根据最小堆的性质,根节点一定是堆中最小的元素,如果小于它,则直接pass,大于的话,就替换掉跟元素,并对根元素进行Heapify,直到源数据遍历结束。

最小堆解决TOPK

最小堆的实现:

public class MinHeap
{
    // 堆的存储结构 - 数组
    private int[] data;

    // 将一个数组传入构造方法,并转换成一个小根堆
    public MinHeap(int[] data)
    {
        this.data = data;
        buildHeap();
    }

    // 将数组转换成最小堆
    private void buildHeap()
    {
        // 完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点,遍历这些结点。
        // *比如上面的图中,数组有10个元素, (data.length) / 2 - 1的值为4,a[4]有孩子结点,但a[5]没有*
        for (int i = (data.length) / 2 - 1; i >= 0; i--) 
        {
            // 对有孩子结点的元素heapify
            heapify(i);
        }
    }

    private void heapify(int i)
    {
        // 获取左右结点的数组下标
        int l = left(i);  
        int r = right(i);

        // 这是一个临时变量,表示 跟结点、左结点、右结点中最小的值的结点的下标
        int smallest = i;

        // 存在左结点,且左结点的值小于根结点的值
        if (l < data.length && data[l] < data[i])  
            smallest = l;  

        // 存在右结点,且右结点的值小于以上比较的较小值
        if (r < data.length && data[r] < data[smallest])  
            smallest = r;  

        // 左右结点的值都大于根节点,直接return,不做任何操作
        if (i == smallest)  
            return;  

        // 交换根节点和左右结点中最小的那个值,把根节点的值替换下去
        swap(i, smallest);

        // 由于替换后左右子树会被影响,所以要对受影响的子树再进行heapify
        heapify(smallest);
    }

    // 获取右结点的数组下标
    private int right(int i)
    {  
        return (i + 1) << 1;  
    }   

    // 获取左结点的数组下标
    private int left(int i) 
    {  
        return ((i + 1) << 1) - 1;  
    }

    // 交换元素位置
    private void swap(int i, int j) 
    {  
        int tmp = data[i];  
        data[i] = data[j];  
        data[j] = tmp;  
    }

    // 获取对中的最小的元素,根元素
    public int getRoot()
    {
            return data[0];
    }

    // 替换根元素,并重新heapify
    public void setRoot(int root)
    {
        data[0] = root;
        heapify(0);
    }
}

利用最小堆获取TopK:

public class TopK
{
    public static void main(String[] args)
    {
        // 源数据
        int[] data = {56,275,12,6,45,478,41,1236,456,12,546,45};

// 获取Top5
        int[] top5 = topK(data, 5);

        for(int i=0;i<5;i++)
        {
            System.out.println(top5[i]);
        }
    }

    // 从data数组中获取最大的k个数
    private static int[] topK(int[] data,int k)
    {
        // 先取K个元素放入一个数组topk中
        int[] topk = new int[k]; 
        for(int i = 0;i< k;i++)
        {
            topk[i] = data[i];
        }

        // 转换成最小堆
        MinHeap heap = new MinHeap(topk);

        // 从k开始,遍历data
        for(int i= k;i<data.length;i++)
        {
            int root = heap.getRoot();

            // 当数据大于堆中最小的数(根节点)时,替换堆中的根节点,再转换成堆
            if(data[i] > root)
            {
                heap.setRoot(data[i]);
            }
        }

        return topk;
}
}

本文分享自微信公众号 - 爱编码(ilovecode)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SAS-一条群消息引发的思考

    看上图,某群友提出将table1的结构转换成table2的结构,这个是一个很明显的转置的操作,也并不特别明显,但是还是很明显的。

    Setup
  • Airtest Project:一款免费的自动化测试工具

    Airtest Project是网易出品的一款自动化解决方案,它适用于任意游戏引擎和应用的自动化测试,并且支持Android和Windows。 Airtest ...

    Altumn
  • SAS Proc transpose过程步

    什么是转置?转置其实就是数据结构的转换,将横向的结构转成纵向的结构,或将纵向转向横向。

    Setup
  • Python笔记:程序设计IPO模式

    程序设计需要按照一定的方法,这样在开发程序的时候才能事半功倍。按照一定的方法进行程序设计,可以清晰的分析问题,处理问题,解决问题。

    Altumn
  • SAS输出RTF精美排版背后的Code

    Proc Template:简单举一例子(仅针对于RTF输出Table,写法很多仅以我常见写法之一为例)

    Setup
  • 一些好用的IDE工具

    Python环境安装完成以后,还需要配置一个程序员专属的工具。正如设计师使用Photoshop作图,产品经理使用Axure做原型图,程序员也有专属的编程工具,叫...

    Altumn
  • SAS-走近Log,实现程序的“风险控制”

    从第一天学习SAS开始,就摆脱不了看SAS日志,每次运行完程序的第一件事,不是看程序运行的结果,而是点击一下Log页面,第二件事也不是去看结果,而是仔细的浏览L...

    Setup
  • 为何说数据结构是程序员最重要的基本功?

    之前我们在自己的用户群中做过一次调研,主要是1-5年编程经验的工程师,有应届生、有小厂的程序员,有大厂的程序员,也有经验不错的技术经理。

    区块链大本营
  • SAS Macro小技巧—获取文件路径

    这样做的的好处是啥呢,每次运行数据或者数据集想实现自动存下来,这个时候就可以用SAS自动创建文件夹的方式来存储。

    Setup
  • FAutoTest:一个免费的H5、小程序自动化测试框架

    FAutoTest是腾讯开源UI自动化测试框架。目前已公开使用,业务涉及腾讯视频、QQ空间、腾讯彩票业务、充值业务、腾讯百科、医疗云等;

    Altumn

扫码关注云+社区

领取腾讯云代金券