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


相关文章
|
8天前
|
JSON Java Apache
非常实用的Http应用框架,杜绝Java Http 接口对接繁琐编程
UniHttp 是一个声明式的 HTTP 接口对接框架,帮助开发者快速对接第三方 HTTP 接口。通过 @HttpApi 注解定义接口,使用 @GetHttpInterface 和 @PostHttpInterface 等注解配置请求方法和参数。支持自定义代理逻辑、全局请求参数、错误处理和连接池配置,提高代码的内聚性和可读性。
|
8天前
|
Java
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式。本文介绍了 Streams 的基本概念和使用方法,包括创建 Streams、中间操作和终端操作,并通过多个案例详细解析了过滤、映射、归并、排序、分组和并行处理等操作,帮助读者更好地理解和掌握这一重要特性。
17 2
|
8天前
|
安全 Java
Java多线程集合类
本文介绍了Java中线程安全的问题及解决方案。通过示例代码展示了使用`CopyOnWriteArrayList`、`CopyOnWriteArraySet`和`ConcurrentHashMap`来解决多线程环境下集合操作的线程安全问题。这些类通过不同的机制确保了线程安全,提高了并发性能。
|
12天前
|
存储 Java 开发者
Java中的集合框架深入解析
【10月更文挑战第32天】本文旨在为读者揭开Java集合框架的神秘面纱,通过深入浅出的方式介绍其内部结构与运作机制。我们将从集合框架的设计哲学出发,探讨其如何影响我们的编程实践,并配以代码示例,展示如何在真实场景中应用这些知识。无论你是Java新手还是资深开发者,这篇文章都将为你提供新的视角和实用技巧。
12 0
|
6月前
|
存储 安全 Java
java集合框架及其特点(List、Set、Queue、Map)
java集合框架及其特点(List、Set、Queue、Map)
|
存储 缓存 安全
Java集合框架(Map篇)
在这个示例代码中,首先定义了一个数组和一个集合,并使用Arrays.asList()方法将数组转换成集合。接着对数组和集合分别进行排序,使用binarySearch()方法查找元素位置,使用copyOf()和copy()方法复制数组和集合,最后输出结果。可以看到,Arrays和Collections提供的方法可以方便地对数组和集合进行操作,节省开发者的时间和精力。
|
6月前
|
Java 程序员
Java集合框架:List、Set、Map类型及泛型详解
Java集合框架:List、Set、Map类型及泛型详解
|
3月前
|
存储 安全 Java
java集合框架复习----(4)Map、List、set
这篇文章是Java集合框架的复习总结,重点介绍了Map集合的特点和HashMap的使用,以及Collections工具类的使用示例,同时回顾了List、Set和Map集合的概念和特点,以及Collection工具类的作用。
java集合框架复习----(4)Map、List、set
|
存储 Java
java集合框架------Map接口与实现类
java集合框架------Map接口与实现类
|
6月前
|
存储 安全 算法
【深入探究Java集合框架】从List到Map的完整指南
【深入探究Java集合框架】从List到Map的完整指南