PHP程序员小白到大牛集训(12期免息)
视频教程分类
推荐视频教程
  • php程序员小白到大牛三个月集训php程序员小白到大牛三个月集训
  • Laravel 9 学习正当时—保姆级教程,想学不会都难!Laravel 9 学习正当时—保姆级教程,想学不会都难!
  • 千万级数据并发解决方案(理论+实战)千万级数据并发解决方案(理论+实战)
  • Laravel基础与实战(模块化)Laravel基础与实战(模块化)
  • 首页 >Java >java教程 > 正文

    Java集合框架之PriorityQueue优先级队列

    转载2022-06-09 11:47:57659 关注公众号:每天精选资源文章推送
    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

    推荐学习:《java视频教程

    Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,本文主要介绍PriorityQueue

    priorityQueue在Java集合框架中的关系如下:

    一、使用PriorityQueue的注意点

    1. 使用时必须导入PriorityQueue所在的包,即:

    import java.util.PriorityQueue

    2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出
    ClassCastException异常

    3. 不能插入null对象,否则会抛出NullPointerException

    4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容

    5. 插入和删除元素的时间复杂度为log以2为底的n

    6. PriorityQueue底层使用了堆数据结构

    7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素(想要变成大堆,需要我们重新比较方法、默认的比较方法是Comparable接口中的compareTo方法)

    二、PriorityQueue常用接口介绍

    1. 优先级队列的构造

    此处只是列出了PriorityQueue中常见的几种构造方式,其他的大家可以参考帮助文档。

    构造器功能介绍
    PriorityQueue()创建一个空的优先级队列,默认容量是11
    PriorityQueue(int
    initialCapacity)
    创建一个初始容量为initialCapacity的优先级队列,注意:initialCapacity不能小于1,否则会抛IllegalArgumentException异
    PriorityQueue(Collection<?
    extends E> c)
    用一个集合来创建优先级队列
    PriorityQueue(Comparator<? super E> comparator)创建具有默认初始容量的优先级队列,并根据指定的比较器对其元素进行比较
    PriorityQueue(int initialCapacity, Comparator <? super E> comparator)

    创建一个初始容量为initialCapacity的优先级队列,根据指定的比较器对其元素进行比较

    注意:initialCapacity不能小于1,否则会抛IllegalArgumentException异

    2、PriorityQueue中对元素的比较

    看完了构造方法,我们重新来思考一个问题

    优先级队列是如何实现有序的呢?因为优先级队列就是借助小根堆来实现的

    在实现小根堆的过程我们知道这其中一定发生了元素的比较,所以PriorityQueue中的元素必须要能够比较大小,那么PriorityQueue是如何进行元素的比较呢?

    PriorityQueue采用了:
    Comparble和Comparator两种方式。

    1. Comparble是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparble接口,并覆写compareTo方法

    2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现Comparator接口并覆写compare方法。

    我们看到这里程序报错了,为什么呢?因为我们插入的Child对象是不可比较的(即没有实现Comparable接口又没有采用自定义的比较器)

    可以看到

    即我们采用了默认的比较方法Comparable接口中的compareTo方法

    此时我们再次看一下报错信息

    看来是在往PriorityQueue中插入元素的时候出现了问题

    那么我们打开PriorityQueue的源码看一下(下面是PriorityQueue中offer方法的源码)

    再看看shiftUp的源码

    继续点进去siftUpComparable

    此时再回过头来看看我们放到PriorityQueue中的Child对象,他即没有自定义比较器又没有实现Comparable接口,当然报错呀!

    那么好吧我们在Child类中实现Comparable接口,按年龄进行比较

    import java.util.PriorityQueue;
    class Child implements Comparable<Child>{
        int age;
        String name;
    
        public Child(int age, String name) {
            this.age = age;
            this.name = name;
        }
    
        @Override
        public int compareTo(Child o) {
            return this.age - o.age;  // 默认实现小根堆
        }
    
        @Override
        public String toString() {
            return "Child{" +
                    "age=" + age +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
    public class TestPriorityQueue {
        public static void main(String[] args) {
            PriorityQueue<Child> priorityQueue = new PriorityQueue<>();
    
            priorityQueue.offer(new Child(12, "小亮"));
            priorityQueue.offer(new Child(11, "小红"));
            priorityQueue.offer(new Child(8, "小强"));
            System.out.println(priorityQueue);
        }
    }

    如果要实现大根堆,也好办

    上面我们是实现了Compable接口,那么如果我们自定义一个年龄比较器呢?

    class Child {
        int age;
        String name;
    
        public Child(int age, String name) {
            this.age = age;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "Child{" +
                    "age=" + age +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
    class AgeComparator implements Comparator<Child> {
    
        @Override
        public int compare(Child o1, Child o2) {
            return o1.age - o2.age; // 实现小根堆
            // return o2.ae - o1.age 实现大根堆
        }
    }
    public class TestPriorityQueue {
        public static void main(String[] args) {
            AgeComparator ageComparator = new AgeComparator();
            // 创建具有默认初始容量的 PriorityQueue ,并根据指定的比较器对其元素进行排序。
            PriorityQueue<Child> priorityQueue = new PriorityQueue<>(ageComparator);
            // 可以看到这里我的Child对象虽然没有实现Comparable接口,但因为我们对Child对象自定义了一个年龄比较器,所以插入元素不会报错
            priorityQueue.offer(new Child(12, "小亮"));
            priorityQueue.offer(new Child(11, "小红"));
            priorityQueue.offer(new Child(8, "小强"));
            System.out.println(priorityQueue);
        }
    }

    3、插入/删除/获取优先级最高的元素

    函数名功能介绍
    boolean
    offer(E e)
    插入元素e,插入成功返回true,如果e对象为空,抛出NullPointerException异常,时
    间复杂度 ,注意:空间不够时候会进行扩容
    E peek()获取优先级最高的元素,如果优先级队列为空,返回null
    E poll()移除优先级最高的元素并返回,如果优先级队列为空,返回null
    int size()获取有效元素的个数
    void
    clear()
    清空

    boolean

    isEmty()

    检测优先级队列是否为空,为空返回true

    推荐学习:《java视频教程

    以上就是Java集合框架之PriorityQueue优先级队列的详细内容,更多请关注php中文网其它相关文章!

    20期PHP线上班

    声明:本文转载于:CSDN,如有侵犯,请联系admin@php.cn删除

  • 相关标签:java
  • 相关文章

    相关视频


    专题推荐