Java集合框架之PriorityQueue优先级队列
本篇文章给大家带来了关于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不能小于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中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

Java 8引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处
