浅浅理解一下堆

这篇具有很好参考价值的文章主要介绍了浅浅理解一下堆。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、堆的定义及本质

二、堆的核心操作

1、向下调整

2、堆的创建

3、向上调整

 三、堆的比较器传入及堆中简单函数的实现

四、堆的应用

1、用于OS调度进程

2、topk问题

 3、堆排序


一、堆的定义及本质

堆在Java中是以优先级队列来表现的(PrityQueue),不传入外部比较器则以小堆来实现(取出最小值)

前提:优先级队列中的元素具备比较能力(1.元素类型本身是可以比较的 2.通过构造方法传入一个外部比较器)

堆的作用:常用来在频繁变动的数据集中找出最值

堆的本质:逻辑上是完全二叉树,本质上是数组

浅浅理解一下堆

堆的定义:

堆总是满足下列性质:

1.堆中某个节点的值总是不大于或不小于其父节点的值;

2、堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构,相当于一维数组,有两个直接后继。

 对于一个结点 2*index+1 是他的左节点 2*index+2是右节点   (index-1)/ 2 可以求得父节点

二、堆的核心操作

1、向下调整

当我们从堆顶取走一个最值时,这时堆的结构已经发生变化,我们往往用堆的最后一个结点来代替堆的根,但此时有可能这个值已经不满足堆的定义,我们需要对其进行向下调整,此时只有堆根部不满足堆的定义

浅浅理解一下堆

 我们此时对根部进行调整

我们首先想到在根的左右结点中找到最小的值来判断是否大于根,如果根已经是最小值,则满足堆的定义,不需要进行交换,否则根与最小值进行交换

 //对堆的根部进行向下调整
    //结束调整的条件?  已经满足堆的结构,无需调整    当前结点已经是叶子结点,下边没有节点,无需调整
    public void justDown(int arr[],int size,int index){
        int left=2*index+1;//判断左子树是否存在,如果没有左子树,必没有右子树(完全二叉树性质)
        while (left<size){
            int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找出左右子树中的最小值
            int largest=arr[index]<=arr[min]?index:min;//在根和最小值中再找出最小值
            if (largest==index) break;//如果根就是最小值 堆结构已满足 退出循环
            swap(arr,index,min);  //不满足交换根和最小值,根等于最小值进行下一次调整
            index=min;
            left=index*2+1;
        }
    }

    private void swap(int[] arr, int index, int min) {
        int temp=arr[index];
        arr[index]=arr[min];
        arr[min]=temp;
    }

2、堆的创建

在我们已经掌握向下调整的情况下,如何将一个完全二叉树调整为堆呢?

我们可以对每个结点进行向下调整,使每个结点都满足堆的定义

但我们知道向下调整的结束条件是当前结点已经满足堆的结构或者当前结点是叶子结点,因此我们没有必要对叶子结点进行调整,而在完全二叉树中我们很容易找到最后一个结点(size-1)是最后一个结点的下标 而他的父节点是(size-1-1)/ 2   那么自他的父节点之后就全是叶子节点

public void creatHeap(int[] arr,int size){
        for (int i=(size-2)/2;i>=0;i--){
            justDown(arr,size,i);
        }
    }

为什么从上到下不行?因为我们向下调整是由要求的,必须左右子树已经是一个堆结构了 如果不理解可以画图。。

浅浅理解一下堆 

在经历一次向下调整时我们发现最小的1永远没有走到顶部的机会,为什么呢,因为我们没有满足向下调整的定义。没有找到真正最小的那个数调整到堆顶 

3、向上调整

在我们创建完成一个堆的时候,往往需要往堆里边添加新的元素,由于我们从数组【0,size)是已经创建好的堆结构,在我们新添加一个元素时,往往需要向上调整

浅浅理解一下堆

public void justUp(int[] arr,int index){
        int parent=(index-1)/2;//父节点下标
        while (arr[index]>arr[parent]){//当子节点大于父节点时我们需要向上调整
            swap(arr,index,parent);
            index=parent;//新的Index是他的父节点
            parent=(index-1)/2;//新的parent结点
        }
    }

 三、堆的比较器传入及堆中简单函数的实现

假设当前有一个person类,里边的属性有姓名和年龄,此时person是默认不支持比较的

 public class person{
        String name;
        int age;
    }

在不修改person类的情况下我们如何实现比较年龄呢?

答案是采用外部比较器

static class PersonComparator implements Comparator<Person>{

        @Override
        public int compare(Person o1, Person o2) {
            return o1.age-o2.age;
        }
    }
 static class PersonComparator implements Comparator<Person>{

        @Override
        public int compare(Person o1, Person o2) {
            return o1.age-o2.age;
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Person> pq=new PriorityQueue(new PersonComparator());
        pq.add(new Person("小明",11));
        pq.add(new Person("小红花",9));
        pq.add(new Person("小刚",21));
        while (!pq.isEmpty()){
            System.out.println(pq.poll().toString());
        }

    }

浅浅理解一下堆

堆的简单函数全实现:

public class MyPriorityQueue{
    long arr[];
    int size;
    public MyPriorityQueue(){//由于我们的元素类型是long类型没有采用泛型,所以不涉及传入比较器
        arr=new long[20];
        size=0;
    }

    public void add(long val){//往堆中加入一个元素
        ensureCapacity();//保证数组空间够用
        arr[size]=val;
        justUp(arr,size);//新加入的元素需要向上调整维持一个堆结构
        size++;
    }

    public long peek(){//查看堆顶部元素
        if (size<0){
            throw new RuntimeException("队列是空的");
        }
        return arr[0];
    }

    public long poll(){//弹出堆顶部的元素
        if (size<0){
            throw new RuntimeException("队列是空的");
        }
        long res=arr[0];//先记录需要返回的元素
        arr[0]=arr[size-1];//把最后一个元素调整到堆的顶部并向下调整
        arr[size-1]=0;//最后一个元素交换到堆顶,那么它就要改为默认值
        size--;
        justDown(arr,size,0);
        return res;
    }

    public int size(){
        return size;
    }

    private void justDown(long[] arr, int size, int index) {
        int left=index*2+1;
        while (left<size){//如果还有子节点(不是叶子节点)
            int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找到左右子结点中的最小值
            int largest=arr[min]<arr[index]?min:index;//找到最小的值
            if (largest==index) break;//如果index本身就是最小值说明他已经满足堆结构不需要调整
            swap(arr,min,index);//交换index和最小值
            index=min;//新的index
            left=index*2+1;//新的最小值
        }
    }

    public void check(){//检查是否满足堆结构
        if (size<0||size>arr.length){
            throw new RuntimeException("size越界");
        }
        for (int i=0;i<size;i++){
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left >= size) {
                // 说明是叶子,跳过
                continue;
            }

            // 左孩子破坏了规则
            if (arr[i] > arr[left]) {
                throw new RuntimeException(String.format("[%d] 位置的值大于其左孩子的值了", i));
            }

            // 右孩子破坏了规则
            if (right < size && arr[i] > arr[right]) {
                throw new RuntimeException(String.format("[%d] 位置的值大于其右孩子的值了", i));
            }
        }
    }

    private void justUp(long[] arr, int index) {
       while (index!=0){
           int parent=(index-1)/2;
           if (arr[parent]<=arr[index]) return;
           swap(arr,index,parent);
           index=parent;
       }
    }

    public boolean isEmpty(){
        return size==0;
    }

    private void ensureCapacity() {
        if (size<arr.length) return;
        arr= Arrays.copyOf(arr,size*2);
    }

    public void swap(long[] arr,int i,int j){
        long temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

四、堆的应用

1、用于OS调度进程

浅浅理解一下堆

2、topk问题

topk问题其实在现实生活有很多场景,比如说淘宝的好物top10等等

假如说我们要在很多数据中找到前k个最大的数  我们有什么思路呢?

1.对所有的数据进行排序再取出前十

这种方法无疑消耗的时间成本和空间成本是是非常高的

时间复杂度达到了O(N*logN) 空间复杂度是O(N)

2.把所有的数据入堆,在取出前k个元素 

第二种方法的时间复杂度相较于第一种减少了很多 大概是O(k*logN),但我们忽略了在数据非常庞大时,堆的向下调整操作往往也需要耗费大量时间,并且空间复杂度也达到了惊人的O(N)

3.我们采用建小堆,小堆的size就是k,如果当前元素比小堆中最小元素大,我们就把它加进去,到最后堆里的元素就是topk

并且空间复杂度也只有O(k)

代码如下:

public class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k==0){ //处理特殊情况,防止堆为空造成的index越界
            return new int[0];
        }
        PriorityQueue<Integer> pq=new PriorityQueue<>(((o1, o2) -> o2-o1));
        for (int i=0;i<k;i++){ //添加k个元素进入堆
            pq.add(arr[i]);
        }
        for (int i=k;i<arr.length;i++){//维持堆中的元素是最小的k个
            if (arr[i]<pq.peek()){
                pq.poll();
                pq.add(arr[i]);
            }
        }
        int[] res=new int[k];//返回这k个元素
        int i=0;
        while (!pq.isEmpty()){
            res[i++]=pq.poll();
        }
        return res;

    }
}

 3、堆排序

堆排序是一种利用堆结构找到最值然后不断取出进行排序,本质上是一种选择排序,不过由于堆找出并维持最值的时间复杂度是O(N*longN)所以他是一种高效的排序

我们把需要排序的数组看  无序加有序的形式 一旦我们找到最值元素 我们就把它交换到最后边

因此总的排序要进行arr.length-1次交换

public void swap(long[] arr,int i,int j){
        long temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public long[] heapSort(long[] nums){
        //首先我们需要建立大堆,把大的元素找出并交换到最后边
        buildHeap(nums);
        for (int i=0;i<nums.length-1;i++){
            swap(nums,0,arr.length-1-i);
            justDown(nums,arr.length-i-1,0);
        }
        return nums;
    }

    private void buildHeap(long[] nums) {
        for (int i=(nums.length-2)/2;i>=0;i--){
            justDown(nums,nums.length,i);
        }
    }

 文章来源地址https://www.toymoban.com/news/detail-404841.html

到了这里,关于浅浅理解一下堆的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 文件目录操作——Linux命令核心

    目录 相对路径和绝对路径  查看和切换工作目录 pwd 显示当前工作目录的绝对路径 cd 切换目录 列出目录内容 ls 列出目录的内容 创建和删除目录文件夹 mkdir创建一个新目录 rmdir 删除一个空的目录 touch 创建空文件 cp复制文件或者目录 rm 删除文件或目录  mv移动文件与目录或重

    2024年02月01日
    浏览(40)
  • 快速上手Linux核心命令(三):文件和目录操作命令

    目录 前言 cd 切换目录 pwd 显示当前路径 ls 显示目录下内容及相关属性信息 mkdir 创建目录 tree 以树形结构显示目录下的内容 touch 创建空白文件或改变文件的时间戳属性 cp 复制文件或目录 mv 移动或重命名文件 rm 删除文件或目录 chown 改变文件或目录的用户用户组 chmod 改变文件

    2023年04月23日
    浏览(52)
  • 浅浅记录一下对某音的X-Agus、X-Gorgon、X-Khronos、X-Ladon研究(仅学习使用)

    近期比较闲,于是对该app进行了逆向研究 前两年也对这个app进行了研究,那时候还没有什么加密参数 可以很正常的进行采集 现在发现连包都抓不到了 于是查看了相关资料 发现该app走的不是正常的http/s协议 于是我hook了传输协议 就可以正常抓包了 抓包后就发现多了好几个加

    2024年01月19日
    浏览(36)
  • 认清现实重新理解游戏的本质

    本文为观后总结:https://www.bilibili.com/video/BV1CT4y1J7ku/ 游戏会成为我们工作和学习拖延的帮凶,游戏对我最大的危害就是拖延, 玩了几十年游戏的人生注定不会过的那么精彩 ,因为所有的精彩都留在了虚拟的游戏世界(游戏开发商服务器数据库里的一条数据) 游戏一直麻痹着

    2024年02月15日
    浏览(40)
  • 线性代数的本质——几何角度理解

    B站网课来自 3Blue1Brown的翻译版,看完醍醐灌顶,强烈推荐: 线性代数的本质 本课程从几何的角度翻译了线代中各种核心的概念及性质,对做题和练习效果有实质性的提高,下面博主来总结一下自己的理解 在物理中的理解是一个有 起点和终点的方向矢量 ,而在计算机科学中

    2024年02月02日
    浏览(60)
  • Go 方法介绍,理解“方法”的本质

    目录 Go 方法介绍,理解“方法”的本质 一、认识 Go 方法 1.1 基本介绍 1.2 声明 1.2.1 引入 1.2.2 一般声明形式 1.2.3 receiver 参数作用域 1.2.4 receiver 参数的基类型约束 1.2.5 方法声明的位置约束 1.2.6 如何使用方法 二、方法的本质 三、巧解难题 我们知道,Go 语言从设计伊始,就不支

    2024年02月06日
    浏览(41)
  • 机器学习基础(一)理解机器学习的本质

            导读: 在本文中,将深入探索机器学习的根本原理,包括基本概念、分类及如何通过构建预测模型来应用这些理论。 目录 机器学习 机器学习概念 相关概念 机器学习根本:模型 数据的语言:特征与标签 训练与测试:模型评估 机器学习的分类 监督学习:有指导

    2024年02月20日
    浏览(28)
  • 本质安全设备标准(IEC60079-11)的理解(四)

    IEC60079-11使用了较长的篇幅来说明设计中需要考虑到的各种间距, 这也从一定程度上说明了间距比较重要,在设计中是需要认真考虑。 从直觉上来讲,间距越大,电路越安全,因为间距比较大,不容易产生电弧。同时间距比较大,也易于散热,从温度角度来说,设备也比较安

    2024年02月15日
    浏览(76)
  • 【云原生-深入理解Kubernetes-1】容器的本质是进程

    大家好,我是秋意零。 😈 CSDN作者主页 😎 博客主页 👿 简介 👻 普通本科生在读 在校期间参与众多计算机相关比赛,如:🌟 “省赛”、“国赛” ,斩获多项奖项荣誉证书 🔥 各个平台, 秋意零/秋意临 账号创作者 🔥 云社区 创建者 点赞、收藏+关注下次不迷路! 欢迎加

    2024年02月02日
    浏览(56)
  • <C++> list容器本质|常用接口|自定义排序规则

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:C++泛型编程 🔥前言 今天把 list 容器的基本操作、常用接口做一个系统的整理,结合具体案例熟悉自定义内部排序方法的使用。 list 与 vector 是STL中最常用的两个容器,如果对vector

    2024年02月01日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包