Java集合框架(PriorityQueue优先级队列讲解)

简介: Java集合框架(PriorityQueue优先级队列讲解)

前言:

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

 

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


6136729e88fe440ba2881e9b068a47ad.png

一、使用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中常见的几种构造方式,其他的大家可以参考帮助文档。

image.png

2、PriorityQueue中对元素的比较

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

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

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


PriorityQueue采用了:

Comparble和Comparator两种方式。

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


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

62cf644e28834ca1946d46b85093ca3b.png


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

可以看到

514b7ee1b7b94b95bc71024d827c16f0.png

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

12359ab31da6414890718ec8e4635328.png

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

9b358385506c4251973f1556f0e39ba8.png

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

 

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

a85492ac28b4486da6b857aaf4ffea11.png

再看看shiftUp的源码

3876af263f874913992e68769f1967f6.png

继续点进去siftUpComparable

4bd2300184834f98ac05c40911221282.png

此时再回过头来看看我们放到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);
    }
}

5fcc6327830540928f0e8730e2f90a1d.png

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

2e75f826db7146559a3f707e14f18c05.png

上面我们是实现了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);
    }
}

6b861a61a54448e7b89ac8ea98a0814f.png

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

image.png


相关文章
|
10天前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
27 3
|
6天前
|
前端开发 Java 数据库连接
Spring 框架:Java 开发者的春天
Spring 框架是一个功能强大的开源框架,主要用于简化 Java 企业级应用的开发,由被称为“Spring 之父”的 Rod Johnson 于 2002 年提出并创立,并由Pivotal团队维护。
23 1
Spring 框架:Java 开发者的春天
|
2天前
|
存储 Java 调度
Java 中的优先队列 PriorityQueue 详解
【10月更文挑战第22天】优先队列 PriorityQueue 是一种非常实用的数据结构,在许多场景中都能发挥重要作用。通过深入了解其特点和用法,我们可以更好地利用它来解决实际问题。
|
5天前
|
SQL Java 关系型数据库
java连接mysql查询数据(基础版,无框架)
【10月更文挑战第12天】该示例展示了如何使用Java通过JDBC连接MySQL数据库并查询数据。首先在项目中引入`mysql-connector-java`依赖,然后通过`JdbcUtil`类中的`main`方法实现数据库连接、执行SQL查询及结果处理,最后关闭相关资源。
|
6天前
|
Java 数据库连接 开发者
Spring 框架:Java 开发者的春天
【10月更文挑战第27天】Spring 框架由 Rod Johnson 在 2002 年创建,旨在解决 Java 企业级开发中的复杂性问题。它通过控制反转(IOC)和面向切面的编程(AOP)等核心机制,提供了轻量级的容器和丰富的功能,支持 Web 开发、数据访问等领域,显著提高了开发效率和应用的可维护性。Spring 拥有强大的社区支持和丰富的生态系统,是 Java 开发不可或缺的工具。
|
6天前
|
安全 Java 程序员
深入Java集合框架:解密List的Fail-Fast与Fail-Safe机制
本文介绍了 Java 中 List 的遍历和删除操作,重点讨论了快速失败(fail-fast)和安全失败(fail-safe)机制。通过普通 for 循环、迭代器和 foreach 循环的对比,详细解释了各种方法的优缺点及适用场景,特别是在多线程环境下的表现。最后推荐了适合高并发场景的 fail-safe 容器,如 CopyOnWriteArrayList 和 ConcurrentHashMap。
34 5
|
8天前
|
安全 Java 程序员
Java集合之战:ArrayList vs LinkedList,谁才是你的最佳选择?
本文介绍了 Java 中常用的两个集合类 ArrayList 和 LinkedList,分析了它们的底层实现、特点及适用场景。ArrayList 基于数组,适合频繁查询;LinkedList 基于链表,适合频繁增删。文章还讨论了如何实现线程安全,推荐使用 CopyOnWriteArrayList 来提升性能。希望帮助读者选择合适的数据结构,写出更高效的代码。
27 3
|
存储 算法 Java
【Java数据结构】堆到底是什么东西?一文帮你理解——优先级队列(堆)
【Java数据结构】堆到底是什么东西?一文帮你理解——优先级队列(堆)
【Java数据结构】堆到底是什么东西?一文帮你理解——优先级队列(堆)
|
3天前
|
监控 安全 Java
在 Java 中使用线程池监控以及动态调整线程池时需要注意什么?
【10月更文挑战第22天】在进行线程池的监控和动态调整时,要综合考虑多方面的因素,谨慎操作,以确保线程池能够高效、稳定地运行,满足业务的需求。
71 38