【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

这篇具有很好参考价值的文章主要介绍了【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:
大家好,我是良辰丫💞💞⛽,我们又见面了,前面我们讲了用链表实现的二叉树,今天我们来接触的概念,堆是一种特殊的二叉树,只不过咱们的对底层原理是数组,堆也是我们在做题中经常见到的,那么,接下来我们就慢慢的去接触堆,认识堆,理解堆,掌握堆。有疑惑可以和我一起讨论交流哦,期待大家的来访。🍬🍬🍬

🧑个人主页:良辰针不戳
📖所属专栏:java数据结构
🍎励志语句:生活也许会让我们遍体鳞伤,但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连,关注,点赞,收藏。
💌作者能力有限,可能也会出错,欢迎大家指正。
💞愿与君为伴,共探Java汪洋大海。

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列



1、堆

1.1 堆的概念

在逻辑上是一种完全二叉树,以顺序结构存储的方式存储的数据,堆的模拟一般用数组,其底层原理往往也是数组。堆分为大根堆和小根堆。

  • 大根堆(最大堆):父亲节点比所有孩子节点都大。
  • 小根堆(最小堆):父亲节点比所有孩子节点都小。

如下图就是一个板板正正的大根堆,每个父亲节点都比所有孩子节点都大,如果去掉下标为6的节点,还可称为大根堆,但是去掉了4号下标的节点就不是堆了,因为堆的概念是完全二叉树,那么为啥这么定义呢?因为在建堆的过程中需要一个个调整,如果不是完全二叉树,就不会调整成唯一的一个序列。

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

总结:

  • 堆的父亲节点总是大于或者小于所有孩子节点。
  • 堆总是一棵完全二叉树。

1.2 堆的基本性质

通过上面我们了解到是一种顺序存储的完全二叉树,对于非完全二叉树,不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节点,就会导致空间利用率比较低。

下图为一个小根堆图,研究性质可以参考下图。

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

i表示节点的下标

  • 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
  • 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
  • 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子

1.3 堆的创建

堆的创建,顾名思义就是把一个个的数据插入到数组中,然后调整即可,一个个传数据太麻烦了,我们直接传入一个数组。调整的时候我们采用向下调整。

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

  1. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)
  2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在
    parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标
    将parent与较小的孩子child比较,如果:
    parent小于较小的孩子child,调整结束
    否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子
    树不满足对的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

下面以创建大根堆为例子。

public void createHeap() {
//usedSize记录堆中元素个数
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }

   //向下调整
    private void shiftDown(int parent,int len) {
    //知道父亲节点,然后扎到左孩子
        int child = 2*parent + 1;
        //要有左孩子
        while (child < len) {
            //一定是有右孩子的情况下
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;
            }
            //child下标 一定是左右孩子 最大值的下标
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
                //左右孩子都比父亲小时跳出循环
            }else {
                break;
            }
        }
    }
  • 在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
  • 调整情况下,最坏的时候,从根一路比较到叶子,比较的次数为完全二叉树的高度。

那么,问题又来了,一颗普通的完全二叉树怎么调整成堆呢?
找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整

public static void createHeap(int[] array) {
int root = ((array.length-2)>>1);
for (; root >= 0; root--) {
shiftDown(array, root);
}
}

注意:
建堆的时间复杂度为O(N)。

1.4 堆插入数据

  • 先将待插入元素放到下标为usedSize的位置。(空间不够时需要扩容)
  • 进行向上调整,直到成为堆。

有的伙伴可能会疑惑了,刚刚学习了向下调整,下载插入数据操作为什么又要向上调整呢?

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

private void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    //向上调整建堆的时间复杂度:N*logN
    public void offer(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
        //向上调整
        shiftUp(usedSize-1);
    }

1.5 堆删除数据

  • 将堆顶元素对堆中最后一个元素交换
  • 将堆中有效数据个数减少一个
  • 对堆顶元素进行向下调整

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

 public void pop() {
        if(isEmpty()) {
            return;
        }
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }
    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

2、优先级队列

说起对列,大家肯定不陌生,因为咱们前面的文章中学习过对列,对列是一种先进先出的数据结构,那么这里的优先级队列又是什么呢?下面我们简单通过一个代码对优先级队列做一个认识。

2.1 初识优先级队列

public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue();
        priorityQueue.offer(3);
        priorityQueue.offer(4);
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
    }

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

咿呀,奇迹出现了,通过上面的运行截图,大家可以发现,优先级队列并不遵守先进先出,而是最小的数据先出来,由此呢?我们可以把它当成一种小根堆

看到这里,大家又产生疑惑,默认为小根堆,那么如果我们想要使用优先队列作为大根堆呢?

办法当然是有的呀,这里我们引入了比较器。那么究竟如何实现呢?我们慢慢往下看。

2.2 比较器Comparator实现优先队列大根堆

看到这里,可能大家会感到疑惑,什么是比较器呢?
java中的对象提供的方法只能比较对象是否相等,而不能比较大小,java提供了一些接口,可以指定对象的属性进行比较,比如,根据学生信息的年龄进行排序。
呜呜呜,看了上面的解释还不明白,没关系,在我上一篇文章中详细介绍了比较器,如果大家对比较器有疑惑,请去具体学习比较器。
对象的比较,点击跳转文章

import java.util.Comparator;
import java.util.PriorityQueue;

class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class Test02 {
    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue<>(new IntCmp());
        priorityQueue.offer(3);
        priorityQueue.offer(4);
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
    }
}

【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

奇迹出现了优先队列通过比较器Comparator修改成了大根堆

注意:
上面的IntCmp类中有自动装包拆包的过程,这里不做详细说明,简单提及一下,Comparator的类型参数不能为基本数据类型,所以只能用包装类Integer,如果想了解更多装包拆包大家可以去自主学习,或者我以后的文章也会更新的。

后序:
堆与优先级队列的学习愉快的结束了,大家肯定受益颇深🐥🐥🐥,知识点全都不难,所谓难的东西也是一个个小小的知识点汇集而成的,不要着急,学习是一个不断探索的过程,心若向阳,路便花开,继续加油🍗🍗🍗!!!文章来源地址https://www.toymoban.com/news/detail-431381.html

到了这里,关于【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Java优先级队列-堆

    大家好,我是晓星航。今天为大家带来的是 Java优先级队列(堆) 的讲解!😀 使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中。 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。 这种方式的主要用法就是堆的表示。 已知双亲(parent)的下

    2023年04月16日
    浏览(40)
  • 【JAVA】优先级队列(堆)

    羡慕别人就让自己变得更好! 优先级队列(堆)可用于topK问题 有大小根堆 注意堆的模拟实现 坚持真的很难但是真的很酷! 队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列。 此时,数据结

    2024年02月15日
    浏览(50)
  • java 堆(优先级队列)详解

    如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki = K2i+1 且 Ki= K2i+2 (Ki = K2i+1 且 Ki = K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小

    2024年02月08日
    浏览(47)
  • 【Java】PriorityQueue--优先级队列

    目录  一、优先级队列  (1)概念 二、优先级队列的模拟实现 (1)堆的概念  (2)堆的存储方式   (3)堆的创建 堆向下调整 (4)堆的插入与删除 堆的插入  堆的删除 三、常用接口介绍 1、PriorityQueue的特性 2、PriorityQueue常用接口介绍   (1)优先级队列的构造 (2)插入

    2024年02月11日
    浏览(46)
  • Java 中的优先级队列详细介绍

    当应该根据优先级处理对象时,将使用 PriorityQueu 。 众所周知 Queue 是 遵循先进先出算法 的,但是有时候需要 按照优先级来处理队列中的元素 ,这时候 PriorityQueue 就派上用场了。 PriorityQueue 基于 优先级堆 。 优先级队列的元素 根据自然顺序排序 ,或者由 队列构造时提供的

    2024年02月14日
    浏览(48)
  • Java 数据结构篇-用数组、堆实现优先级队列

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 优先级队列说明         2.0 用数组实现优先级队列         3.0 无序数组实现优先级队列         3.1 无序数组实现优先级队列 - 入队列 offer(E value)         3.2 无序数组实现优先

    2024年02月04日
    浏览(45)
  • Java【优先级队列】详细图解 / 模拟实现 + 【PriorityQueue】常用方法介绍

    📕各位读者好, 我是小陈, 这是我的个人主页 📗小陈还在持续努力学习编程, 努力通过博客输出所学知识 📘如果本篇对你有帮助, 烦请点赞关注支持一波, 感激不尽 📙 希望我的专栏能够帮助到你: JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统

    2024年02月07日
    浏览(49)
  • 华为OD机试 - 支持优先级的队列(Java & JS & Python)

    题目描述 实现一个支持优先级的队列,高优先级先出队列;同优先级时先进先出。 如果两个输入数据和优先级都相同,则后一个数据不入队列被丢弃。 队列存储的数据内容是一个整数。 输入描述 一组待存入队列的数据 (包含内容和优先级) 输出描述 队列的数据内容(优先级

    2024年02月13日
    浏览(48)
  • 【华为OD统一考试B卷 | 100分】支持优先级的队列(C++ Java JavaScript Python)

    在线OJ 已购买本专栏用户,请私信博主开通账号,在线刷题!!! 运行出现 Runtime Error 0Aborted,请忽略 华为OD统一考试A卷+B卷 新题库说明 2023年5月份,华为官方已经将的 2022/0223Q(1/2/3/4)统一修改为OD统一考试(A卷)和OD统一考试(B卷)。 你收到的链接上面会标注A卷还是B卷。

    2024年02月13日
    浏览(40)
  • Linux_进程的优先级&&环境变量&&上下文切换&&优先级队列

    什么是优先级? 指定一个进程获取某种资源的先后顺序 本质是进程获取cpu资源的优先顺序 为什么要有优先级 进程访问的资源(CPU)是有限的 操作系统关于调度和优先级的原则:分时操作系统,基本的公平,如果进程因为长时间不被调整,就造成了饥饿问题 Linux的优先级特

    2024年04月09日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包