关键词：

数据结构中的堆：（Heap）

• 一、堆的概念：
• 二、堆的操作：
• • 1、向下调整（小堆为例）
  • 2、向上调整（大堆为例）
  • 3、建堆：
• 三、堆的应用：
• • 1、堆排序
  • 2、TopK
  • 3、优先级队列(Priority Queue)

一、堆的概念：

• 堆 逻辑上 是一棵 完全二叉树
• 堆 物理上 是保存在 数组 中
• 满足 任意结点的值 都 大于 其 子树中结点的值，叫做大堆，或者大根堆，或者最大堆
• 满足 任意结点的值 都 小于 其 子树中结点的值，则是小堆，或者小根堆，或者最小堆
• 堆的基本作用是，快速找集合中的最值

二、堆的操作：

1、向下调整（小堆为例）

重要操作：

（前提：只有需要调整的位置不清楚，但其他位置已经满足堆的性质和了）

伪代码思路：

引出的问题：

1、怎么判断 index 对应的位置是不是叶子结点 ？

2、怎么找最小的孩子？

3、小堆是有序的吗？有序的是小堆吗？

小堆不一定是有序的，但有序的一定是小堆。

代码实现：

public class HeapTest 
    public static void shiftDown(int[] array, int size, int index) 
        while (true) 
            //1.判断 index 对应的下标是不是叶子结点
            int leftIndex = 2 * index + 1;
            if(leftIndex >= size) 
                return;
            

            //2.找到两个孩子中最小的
            int minIndex = leftIndex;
            int rightIndex = leftIndex + 1;
            if(rightIndex < size && array[rightIndex] < array[leftIndex]) 
                minIndex = rightIndex;
            

            //3.最小的孩子的值和 index 对应位置的值比较
            if(array[index] <= array[minIndex]) 
                return;
            

            //4.交换最小的孩子的值和 index 的值
            int temp = array[index];
            array[index] = array[minIndex];
            array[minIndex] = temp;

            //5.把最小的孩子视为 index，循环回去（从步骤 1，继续往下走）
            index = minIndex;
        
    

2、向上调整（大堆为例）

思路：伪代码分析

public static void adjustUp(int[] array,int size,int index) 
	1.判断 index 是不是树的根,如果是根，调整结束
	2.找到 index 的父结点
	3.比较父结点的值和 index 的值
	4.只要父结点的值 > index，调整结束
	5.交换父结点和 index 的值
	6.把父结点看做 index，继续这个大循环

代码实现：

public class HeapTest 
    public static void adjustUp(int[] array,int size,int index) 
        while (true) 
            //1.判断 index 是不是树的根,如果是根，调整结束
            if(index == 0) 
                break;
            
            
            //2.找到 index 的父结点
            int parentIndex = (index - 1) / 2;
            
            //3.比较父结点的值和 index 的值
            //4.只要父结点的值 > index，调整结束
            if(array[parentIndex] > array[index]) 
                break;
            
            
            //5.交换父结点和 index 的值
            int temp = array[index];
            array[index] = array[parentIndex];
            array[parentIndex] = temp;
            
            //6.把父结点看做 index，继续这个大循环
            index = parentIndex;

        
    

3、建堆：

public static void createHeap(int[] array, int size) 
	//找到层序遍历的最后一个结点下标
	int lastIndex = size - 1;
	
	//找到最后一个结点的父节点的下标
	int lastParentIndex = lastIndex - 1 / 2;
	
	//从[(size-2)/2,0] 不断地进行向下调整
	for(int i = lastParentIndex; i >= 0; i++) 
		shiftDown(array,size,i);
	

三、堆的应用：

堆的应用有挺多：优先级队列、堆排序、TopK。

---

1、堆排序

分为两个步骤：

• 1、用当前需要排序的数据构建一个堆
• 2、不断的弹出当前堆的堆顶元素，因为小顶堆的堆顶元素一定是最小的，即可以用于排序。堆排序的本质就是，把数据构建成堆之后，弹出堆顶元素，然后互换堆顶元素和最后一个元素，不断对当前堆进行自顶向下的堆的调整，然后继续弹出。

---

2、TopK

TopK一般解决的是求解前K个最大或者最小的元素，或第K个最大或最小的元素。

拿到这类问题，我们的第一想法肯定是排序求解。但排序还会浪费一定的资源排序前K个元素，为了节省计算资源，我们需要思考的是怎么优化，聪明的你肯定想到了，是不是这最大的k个元素也不需要排序呢？

为此，我们需要构建包含K个元素的小顶堆，这个小顶堆用于存储，当前最大的k个元素。接着我们需要从第 k+1个元素开始扫描，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。扫描完所有n-k个元素，最终堆中的k个元素，就是优化后求的TopK。

---

3、优先级队列(Priority Queue)

入队列操作
过程（以大堆为例）：

出队列操作
过程（以大堆为例）：

代码实现：

public class MyPriorityQueue 
    private Integer[] array;
    private int size;

    public MyPriorityQueue() 
        array = new Integer[100];
        size = 0;
    

    public Integer element() 
        if(size == 0) 
            throw new RuntimeException("空的");
        
        return array[0];
    

    /**
     * 入队列
     */
    public void add(Integer e) 
        array[size] = e;
        size++;
        adjustUp(size-1);
    

    public void adjustUp(int index) 
        while (true) 
            if(index == 0) 
                break;
            
            int parentIndex = (index - 1) / 2;
            if(array[parentIndex] <= array[index]) 
                break;
            
            int temp = array[index];
            array[index] = array[parentIndex];
            array[parentIndex] = temp;
            index = parentIndex;
        
    

    /**
     * 出队列
     */
    public Integer remove() 
        if(size == 0) 
            throw new RuntimeException("空的");
        

        int e = array[0];
        array[0] = array[size - 1];
        size--;

        adjustDown(0);
        return e;

    

    private void adjustDown(int index) 
        while (true) 
            int leftIndex = 2 * index + 1;
            if(leftIndex >= size) 
                return;
            
            int minIndex = leftIndex;
            int rightIndex = leftIndex + 1;
            if(rightIndex < size && array[rightIndex] < array[leftIndex]) 
                minIndex = rightIndex;
            

            if(array[index] <= array[minIndex]) 
                return;
            

            int temp = array[index];
            array[index] = array[minIndex];
            array[minIndex] = temp;

            index = minIndex;
        
    

一篇带你看懂flutter叠加组件stack(代码片段)

注意：无特殊说明，Flutter版本及Dart版本如下：Flutter版本：1.12.13+hotfix.5Dart版本：2.7.0StackStack组件可以将子组件叠加显示，根据子组件的顺利依次向上叠加，用法如下：Stack(children:<Widget>[Container(height:200,width:200,color:Colors.red,)... 查看详情

一篇带你看懂flutter叠加组件stack(代码片段)

注意：无特殊说明，Flutter版本及Dart版本如下：Flutter版本：1.12.13+hotfix.5Dart版本：2.7.0StackStack组件可以将子组件叠加显示，根据子组件的顺利依次向上叠加，用法如下：Stack(children:<Widget>[Container(height:200,width:200,color:Colors.red,)... 查看详情

全干货5分钟带你看懂docker！

...本文从Docker定义，作用，技术架构，安装和使用等全方位带你看懂Docker。Docker是啥？打开翻译君输入Docker结果显示码头 查看详情

10个问题带你看懂composemultiplatform1.0(代码片段)

近日JetBrains正式发布了ComposeMultiplatform1.0版，这标志其在生产环境中使用的时机已经成熟。相信有不少人对它还不太熟悉，本文通过下面10个热门问题带大家认识这一最新的跨平台技术。FAQ：与JetpackCompose的关系?是否... 查看详情

5分钟带你看懂prettier+eslint搭配（vscode）(代码片段)

    最近身边不少朋友在用eslint和prettier搭配的时候，总是遇到一些莫名其妙的报错，自己也不知道怎么配，所以我总结了一下自己搭配的步骤，分享一下，如有不对之处，静请诸位大佬雅正！    ... 查看详情

一篇文章带你看懂cloudflare信息泄露事件

版权声明：本文由贺嘉   原创文章，转载请注明出处: 文章原文链接：https://www.qcloud.com/community/article/753847001488039974来源：腾云阁 https://www.qcloud.com/community 1.问题描述近期根据HackerNews的报道，以及国际CDN厂... 查看详情

三个问题带你看懂多核并发框架skynet源码

三个问题带你看懂多核并发框架skynet源码|actor是什么？actor怎么调度？actor跟网络怎么绑定？专注于服务器后台开发，包括C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，Mo 查看详情

一分钟带你看懂公有云和私有云的区别

私有云和公有云的显著差别在于对数据的掌控。只需一分钟，下面几张图就能让你看懂公有云和私有云的本质区别。私有云和公有云的显著差别在于对数据的掌控。采用公有云服务的企业必须将数据托管于云服务商的数据中心，... 查看详情

分类vs标签，一文带你看懂数据中台为什么要建标签体系？

...自行订阅，你的支持就是我不断更新的动力哟！MATLAB-30天带你从入门到精通MATLAB深入理解高级教程（附源码）tableau可视化数据分析高级教程因此，有专家吐槽：“现在讲啥数据标签，数据类目，跟SAPCl 查看详情

百万奖池角逐，华为云iot边缘带你看懂“边缘计算开发者大赛”

摘要：2022年9月1日，第二届边缘计算开发者大赛正式启动。2022年9月1日，第二届边缘计算开发者大赛正式启动！本届大赛由华为云参与承办，中国信息通信研究院、工业互联网产业联盟、边缘计算产业联盟共... 查看详情

深入浅出丨带你看懂数据可视化「美」的历程

深入浅出丨带你看懂数据可视化「美」的历程古人说：“人不可貌相”，但从古至今，人类却是一群感性动物，容易受到外在表象影响，先感性才理参考技术A深入浅出丨带你看懂数据可视化「美」的历程古人说：“人不可... 查看详情

我用140行代码，带你看一场流星雨⭐(代码片段)

我用140行代码，带你看一场流星雨⭐📣大家好，我叫小丞同学，今天走个治愈风，来做一个治愈系的流星雨效果前言在一个夜深人静的晚上，程序员小丞坐在屋顶上，看着屏幕上满屏的error，心里... 查看详情

我用140行代码，带你看一场流星雨⭐(代码片段)

我用140行代码，带你看一场流星雨⭐📣大家好，我叫小丞同学，今天走个治愈风，来做一个治愈系的流星雨效果前言在一个夜深人静的晚上，程序员小丞坐在屋顶上，看着屏幕上满屏的error，心里... 查看详情

手把手教你看懂zookeeper的选举过程(代码片段)

小白都能看懂Zookeeper的选举过程1.前提知识要点正式版ZAB协议:Zookeeper是非常重要的分布式协调组件，需要进行集群部署，集群中会以一主多从的形式进行部署。Zookeeper为了保持数据的一致性，使用了ZAB协议，这个... 查看详情

阿昌教你看懂mybatisplus的sqlsessionfacotry的创建过程(代码片段)

前言前置版本：MybatisPlus3.0.5这几天阿昌又开始研究mybatisplus的内容，我就先开始研究mybatis在springboot的环境下，是如何进行对SqlSessionFacotry类进行创建注入的。这里就记录下自己学习到的内容。感谢各位大佬的观看•̀... 查看详情

阿昌教你看懂mybatisplus的sql语句的创建过程(代码片段)

前言前置版本：MybatisPlus3.0.5前些日子，阿昌写过一篇【mybatisplus的SqlSessionFacotry的创建过程】的菜鸡文章，这里我打算再记录一篇，关于mybatisplus的sql语句的创建过程。前戏同样，学过springboot的人都知道，... 查看详情

阿昌教你看懂springmvc执行流程(代码片段)

阿昌教你看懂SpringMVC执行流程一、前言Hello呀！！！阿昌又来也╰(°▽°)╯!!!SpringMVC的执行流程大家应该都挺熟悉的，但是真的去debug源码的人应该算少数，这里阿昌一直都想自己记录一下debug-SpringMVC的执行流... 查看详情

阿昌教你看懂springmvc执行流程(代码片段)

阿昌教你看懂SpringMVC执行流程一、前言Hello呀！！！阿昌又来也╰(°▽°)╯!!!SpringMVC的执行流程大家应该都挺熟悉的，但是真的去debug源码的人应该算少数，这里阿昌一直都想自己记录一下debug-SpringMVC的执行流... 查看详情