优先队列的数据结构_低优先级队列一天只能一场

优先队列的数据结构_低优先级队列一天只能一场目录一.PriorityQueuePriorityQueue简介继承关系PriorityQueue示例二.Comparable比较器Compara接口三.Comparator比较器Comparator接口四.底层原理一.PriorityQueuePriorityQueue简介PriorityQueue,即优先级队列。优先级队列可以保证每次取出来的元素都是队列中的最小或最大的元素<Java优先级队列默认每次取出来的为最小元素&gt.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

目录

一. PriorityQueue

PriorityQueue 简介

继承关系

PriorityQueue 示例

二. Comparable 比较器

Compare 接口

三. Comparator 比较器

Comparator 接口

四. 底层原理


一. PriorityQueue

PriorityQueue 简介

PriorityQueue ,即优先级队列。优先级队列可以保证每次取出来的元素都是队列中的最小最大的元素<Java优先级队列默认每次取出来的为最小元素>。

大小关系:元素的比较可以通过元素本身进行自然排序,也可以通过构造方法传入比较器进行比较。

继承关系

优先队列的数据结构_低优先级队列一天只能一场

通过继承关系图可以知道 PriorityQueueQueue 接口的一个实现类,而 Queue 接口是 Collection 接口的一个实现类,因此其拥有 Collection 接口的基本操作,此外,队列还提供了其他的插入,移除和查询的操作。每个方法存在两种形式:一种是抛出异常(操作失败时),另一种是返回一个特殊值(null 或 false)。

优先队列的数据结构_低优先级队列一天只能一场

 PriorityQueuepeekelement 操作的时间复杂度都为常数,add,offer,remove 以及 poll 的时间复杂度是 log(n)。

PriorityQueue 示例

impot java.util.PriorityQueue;

public class PriorityQueueTest{
    public static void main(String[] args){
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(11);
        queue.add(22);
        queue.add(33);
        queue.add(55);
        queue.add(44);
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
    }
}

运行结果:

优先队列的数据结构_低优先级队列一天只能一场

代码中我们依次添加11,22,33,55,44五个数据,然后进行删除,通过结果我们发现,每次删除的都为队列中最小元素,即体现了优先级队列。

结论:优先级队列默认每次获取队列最小的元素,也可以通过 comparator 比较器来自定义每次获取为最小还是最大。

注意:优先级队列中不可以存储 null

二. Comparable 比较器

Compare 接口

public interface Comparable<T>{
    public int compareTo(T o);
}

该接口只存在一个 public int compareTo(T o); 方法,该方法表示所在的对象和 o 对象进行比较,返回值分三种:

1:表示该对象大于 o 对象

0:表示该对象等于 o 对象

-1:表示该对象小于 o 对象

需求:在优先级队列中存储对象学生,每个学生有 id,name 两个属性,并且使优先级队列每次按照学生的 id 从小到大取出。

代码示例:

Student 类:当前类实现了 Comparable 接口,即当前类提供了默认的比较方法。

    public class Student implements Comparable{
        private int id;
        private String name;
        
        public Student(int id,String name,int age){
            this.id = id;
            this.name = name;
        }
        
        public int getId(){
            return id;
        }
        
        @Override
        public String toString(){
            return "Student{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
        
        @Override
        public int compareTo(Object o){
            Student o1 = (Student)o;
            return this.id - o1.id;
        }
    }

PriorityQueueTest 类:

public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>();
        queue.add(new Student(2,"Jack"));
        queue.add(new Student(1,"Mary"));
        queue.add(new Student(5,"Mcan"));
        queue.add(new Student(4,"Scolt"));
        queue.add(new Student(3,"Tina"));
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
    }
}

运行结果:

优先队列的数据结构_低优先级队列一天只能一场

三. Comparator 比较器

新需求:如果使优先级队列按照学生 id 从大到小取出呢?我们很快就会想到修改 Student 类的compareTo 方法,使 return o1.id – this.id;这样当然可以实现我们的新需求。但是有很多时候类的compareTo 方法是不能修改的,比如 JDK 给我们提供的源代码,在不修改 compareTo 方法的前提下实现需求,只能用 comparator 比较器了。

Comparator 接口

public interface Comparator<T>{
    int compare(T o1,T o2);
}

该接口只存在一个 int compare(T o1,T o2);方法,该方法需要参数是两个待比较的对象,返回结果是 int 类型:

1:表示 o1对象 大于 o2 对象

0:表示 o1对象 等于 o2 对象

-1:表示 o1对象 小于 o2 对象

public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>(new Comparator<Student>() {

            @Override
            public int compare(Student o1, Student o2) {
                return o2.getId() - o1.getId();
        }
    })
    queue.add(new Student(2, "Jack"));
    queue.add(new Student(1, "Mary"));
    queue.add(new Student(5, "Mcan"));
    queue.add(new Student(4, "Scolt"));
    queue.add(new Student(3, "Tina"));
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
}
}

运行结果:

优先队列的数据结构_低优先级队列一天只能一场

四. 底层原理

优先级队列是如何保证每次取出的是队列中最小(最大)的元素的呢?查看源代码,底层的存储结构为一个数组

transient Object[] queue;

表面上是一个数组结构,实际上优先队列采用的是堆的形式来进行存储的,通过调整小堆大堆保证每次取出的元素为队列中的最小或最大。

详见:https://blog.csdn.net/Lucky_mzc/article/details/123331280?spm=1001.2014.3001.5501

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/190435.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • goland 激活码(注册激活)

    (goland 激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~MLZPB5EL5Q-eyJsaWNlbnNlSWQiOi…

  • 使用工具清理Windows的winsxs目录

    使用工具清理Windows的winsxs目录一、使用软件工具清理1、使用DriverStoreExplorer清理DriverStoreExplorer下载地址:https://github.com/lostindark/DriverStoreExplorer/releases/download/v0.11.64/DriverStoreExplorer.v0.11.64.zip使用方法:(1)双击运行(使用管理员)(2)点击“选取旧的驱动”,之后点击“删除驱动包”2、使用Winsxs清理工具笔者吐槽:这个软件提供的论坛我上去看

    2022年10月28日
  • Sobel 算子结构

    Sobel 算子结构Sobel算子结构

  • a标签下划线的坑

    a标签下划线的坑问题来源描述在使用Vux的tabbar组件,发现底部导航文字会有下划线,用chrome的开发者工具去找到该标签,发现就是一个span,利用各种CSS手段去删除下划线,都不起作用,但是删除这个span标签文字就消失了,span的样式里面也没有出现让其产生下划线的样式,绞尽脑汁去想各种CSS或者是JS能让span控件产生下划线的东西,一点头绪都没有。后面想想唯一的可能性就是a标签了,于是往上去找s…

  • Java反射机制的原理和用途

    Java反射机制的原理和用途看了好多关于Java反射机制的文章,大多都太过官方,消化起来比较稍显费劲,本篇,我会依据自己的理解去阐述什么是Java的反射机制,反射用在什么地方,以及怎么来使用?开篇前,我们还是要了解一下,什么是Java的反射机制:“程序运行时,允许改变程序结构或变量类型,这种语言称为动态语言”。从这个观点看,Perl、Python(看过我写的Python3学习系列的博文,不止一次突出…

  • SIGPIPE信号问题

    SIGPIPE信号问题
    socket编程问题
    SIGPIPE信号问题=========================
    当服务器close一个连接时,若client端接着发数据。根据TCP协议的规定,会收到一个RST响应,client再往这个服务器发送数据时,系统会发出一个SIGPIPE信号给进程,告诉进程这个连接已经断开了,不要再写了。
       根据信号的默认处理规则SIGPIPE信号的默认执行动作是terminate(终止、退出),所以client会退出。若不想客户端退出可以把SIGP

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号