深入理解PriorityQueue(优先级队列):工作机制与内部构造解析
目录
1.什么是优先级队列?
2.优先级队列的特性
3. 如何使用优先级队列
4.JDK源码分析
4.1类的继承关系
4.2类的属性
4.3常用的方法
5.自定义优先级队列实现
5.1 优先级队列类定义
5.2 add()方法
5.3 remove()方法
5.4 removeAt()方法
5.5 完整代码
1.什么是优先级队列?
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。
在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有*先出(first in, largest out)的行为特征。通常采用堆数据结构来实现。
根据jdk源码中的描述:
优先级队列表示为平衡二进制堆:队列[n]的两个子级是队列[2*n+1]和队列[2*(n+1)]。
优先级队列由comparator排序,如果comparator为null,则由元素的自然顺序排序:对于堆中的每个节点n和n的每个后代d,n<=d。假设队列不为空,则值最低的元素位于队列[0]中。
2.优先级队列的特性
-
PriorityQueue是非线程安全,PriorityBlockingQueue是线程安全的,基于BlockingQueue接口实现。
-
优先级队列就相当于有一个任务调度系统 给每一个任务排一个优先级 所有的任务放到优先级队列 执行任务的线程会从队列中选择一个优先级最高的任务执行。
-
PriorityQueue基于优先堆(大根堆/小根堆),在默认情况下使用的是小根堆,这个优先队列可以默认自然排序或者通过提供的Compartor(比较器)在队列实例化的时候进行排序。
-
不允许null元素 不支持non-comparable元素
3. 如何使用优先级队列
分别创建了一个普通队列和一个优先级队列,优先级队列的排序采用的是Person类中的id大小进行排序的。
class Person{
private int id;
private String name;
public Person(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "Person{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
public class TestDemo7 {
public static Comparator<Person> idComparator = new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o2.getId() - o1.getId();
}
};
public static void main(String[] args) {
//练习1:
Queue<Integer> integerPriorityQueue = new PriorityQueue<>();
for(int i=0; i<10; i++){
integerPriorityQueue.add(new Integer(new Random().nextInt(100)));
}
for(int i=0; i<10; i++){
Integer in = integerPriorityQueue.remove();
System.out.println("priority queue: "+in);
}
//练习2:
Queue<Person> personPriorityQueue = new PriorityQueue<>(idComparator);
for(int i=0; i<10; i++){
int id=new Random().nextInt(100);
personPriorityQueue.add(new Person(id, "person"+id));
}
for(int i=0; i<10; i++){
Person per = personPriorityQueue.remove();
System.out.println("person priority queue: "+per);
}
}
}
4.JDK源码分析
4.1类的继承关系
- PriorityQueue基于Queue接口实现,在Queue接口和PriorityQueue具体实现类间提供了一个AbstractQueue抽象类
- PriorityQueue是一个
4.2类的属性
-
private static final int DEFAULT_INITIAL_CAPACITY = 11;//默认容量
-
transient Object[] queue;//底层实现数组
-
private int size = 0;//有效元素个数
-
private final Comparator<? super E> comparator;//按照比较器对象进行排序
-
transient int modCount = 0;//修改次数
4.3常用的方法
- add()与offer()
add()和offer()都是向队列中添加一个元素。一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,调用 add() 方法就会抛出一个 unchecked 异常,而调用 offer() 方法会返回 false,因此就可以在程序中进行有效的判断。
- remove()与poll()
remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空,调用remove() 的行为与 Collection 接口的版本相似会抛出异常,但是新的 poll() 方法在用空集合调用时只是返回 null,因此新的方法更适合容易出现异常条件的情况。
- grow()扩容函数,扩的容量为minCapacity
对于这里的扩容,为了让数组的长度为一个素数,从而保证为一个完全二叉树。
- element()和peek()
element()
和peek()
的语义完全相同,都是获取但不删除队首元素,也就是队列中权值最小的那个元素,二者唯一的区别是当方法失败时前者抛出异常,后者返回null
。根据小顶堆的性质,堆顶那个元素就是全局最小的那个;由于堆用数组表示,根据下标关系,0
下标处的那个元素既是堆顶元素。所以直接返回数组0
下标处的那个元素即可。
-
siftDownUsingComparator()
k为根节点,用c保存左孩子,左孩子k*2+1,右孩子k*2+2,如果右孩子存在并且右孩子要比左孩子小,将右孩子赋给c,并进行下标更新,之后与x进行比较,如果x还小就break不用进行调整,否则就将c给k位置,然后进行位置更新,最后将x赋值给k位置。
5.自定义优先级队列实现
5.1 优先级队列类定义
优先级队列基于数据结构堆(默认小根堆)去实现,而堆常用数组实现,因此在类中定义一个泛型数组,size为有效元素个数,初始容量设为5。
public class MyPriorityQueue<E extends Comparable<E>> {
private E[] queue;
private int size;
private static final int initalCapacity = 5;
public MyPriorityQueue(){
this(initalCapacity);
}
public MyPriorityQueue(int initalCapacity){
queue = (E[])new Comparable[initalCapacity];
}
}
5.2 add()方法
该方法用于向优先级队列中添加元素。
1).在进行添加元素的时候,首先要判断当前容量是否已满,如果满了需要进行扩容。
2).当队列为空时,直接赋值给首位元素,szie自增
3). 正常情况下,添加元素后,可能会导致堆不是小根堆,因此利用adjustUP()进行向上调整。
因为底层基于数组,0号元素就是顶点,size-1为最后一个节点。
由子节点下标推父节点下标,当子节点下标为index时,父节点为(index-1)/2.
利用while循环对当前位置节点与其父节点依次进行比较,若父节点大于当前value,将父节点值给当前位置,然后记录父节点下标继续判断,若父节点不大于当前节点值,则现在已经是小根堆,不必调整了,循环结束后将value赋值给index位置。
public void add(E value){
//容量不足扩容
if(size == queue.length){
queue = Arrays.copyOf(queue, queue.length<<1);
}
//队列为空
if(size == 0){
queue[0] = value;
size++;
}
else{
adjustUP(size, value);
size++;
}
}
public void adjustUP(int index, E value){
//向上调整
while(index > 0){
//由子节点推父节点下标
int parentIndex = (index-1)/2;
//若父节点大于当前value,将父节点值给当前位置,然后记录父节点下标继续判断
if(queue[parentIndex].compareTo(value) > 0){
queue[index] = queue[parentIndex];
index = parentIndex;
}
//若父节点不大于当前节点值,则现在已经是小根堆,不必调整了
else{
break;
}
}
//将value赋给index位置
queue[index] = value;
}
5.3 remove()方法
该方法用于删除根节点,同add方法类似,首先对队列进行判空,然后考虑队列只有一个元素的情况。
在正常情况下,要保证底层维护的是一个小根堆,删除的是0号位置元素,因此要把最后一个节点放到0号位置。
首先将0号位置置空,然后进行向下调整。
在向下调整的过程中,由于并不知道根节点的左右孩子哪个值较小,因此要进行判断,并分别用minIndex和minValue记录较小值的下标和值,然后将value与这个较小值进行比较,如果根节点小于minValue直接break,不用调整了,本身就还是小根堆,否则就将minValue赋值给index位置,然后进行下标更新。循环结束后将value赋值给queue[index]。
public boolean remove(){
//删除根节点元素
//判空
if(size == 0){
return false;
}
//当前队列只有一个元素
if(size == 1){
queue[size-1] = null;
return true;
}
//正常情况,保证底层维护的是一个小根堆,删除的是0号位置元素,把最后一个节点放到0号位置
queue[0] = null;
adjustDown(0,queue[--size]);
return true;
}
public void adjustDown(int index, E value){
//向下调整
while (index < (size>>1)){
int leftChild = index*2 + 1;
int rightChild = index*2 + 2;
//保存两个孩子中最小孩子的下标
int minIndex = 0;
//保存当前的最小值
E minValue = null;
//找左右孩子的最小值
if(rightChild < size && queue[leftChild].compareTo(queue[rightChild]) >= 0){
minValue = queue[rightChild];
minIndex = rightChild;
}
if(value.compareTo(minValue) < 0){
break;
}
queue[index] = minValue;
index = minIndex;
}
queue[index] = value;
}
5.4 removeAt()方法
public boolean remove(E target){
//删除指定元素
int index = -1;
//找到target所在的位置点
for (int i = 0; i < size; i++) {
if(target.equals(queue[i])){
index = i;
break;
}
}
//保证队列中有这样的位置点
if(index == -1){
return false;
}
//特殊情况,删除的是最后一个元素
if(size-1 == index){
queue[--size] = null;
return true;
}
//正常情况下
else {
queue[index] = null;
adjustDown(index, queue[size - 1]);
//特殊情况
if (queue[index] == queue[size - 1]) {
adjustDown(index, queue[size - 1]);
}
queue[--size] = null;
return true;
}
}
5.5 完整代码
package sefl.January;
import java.util.Arrays;
/**
* Description :
* Created by Resumebb
* Date :2021/1/7
*/
public class MyPriorityQueue<E extends Comparable<E>> {
private E[] queue;
private int size;
private static final int initalCapacity = 5;
public MyPriorityQueue(){
this(initalCapacity);
}
public MyPriorityQueue(int initalCapacity){
queue = (E[])new Comparable[initalCapacity];
}
public void add(E value){
if(size == queue.length){
queue = Arrays.copyOf(queue, queue.length<<1);
}
if(size == 0){
queue[0] = value;
size++;
}
else{
adjustUP(size, value);
size++;
}
}
public void adjustUP(int index, E value){
//向上调整
while(index > 0){
//由子节点推父节点下标
int parentIndex = (index-1)/2;
//若父节点大于当前value,将父节点值给当前位置,然后记录父节点下标继续判断
if(queue[parentIndex].compareTo(value) > 0){
queue[index] = queue[parentIndex];
index = parentIndex;
}
//若父节点不大于当前节点值,则现在已经是小根堆,不必调整了
else{
break;
}
}
//将value赋给index位置
queue[index] = value;
}
public boolean remove(){
//删除根节点元素
//判空
if(size == 0){
return false;
}
//当前队列只有一个元素
if(size == 1){
queue[size-1] = null;
return true;
}
//正常情况,保证底层维护的是一个小根堆,删除的是0号位置元素,把最后一个节点放到0号位置
queue[0] = null;
adjustDown(0,queue[--size]);
return true;
}
public void adjustDown(int index, E value){
//向下调整
while (index < (size>>1)){
int leftChild = index*2 + 1;
int rightChild = index*2 + 2;
//保存两个孩子中最小孩子的下标
int minIndex = 0;
//保存当前的最小值
E minValue = null;
//找左右孩子的最小值
if(rightChild < size && queue[leftChild].compareTo(queue[rightChild]) >= 0){
minValue = queue[rightChild];
minIndex = rightChild;
}
if(value.compareTo(minValue) < 0){
break;
}
queue[index] = minValue;
index = minIndex;
}
queue[index] = value;
}
public boolean removeAt(E target){
//删除指定元素
int index = -1;
//找到target所在的位置点
for (int i = 0; i < size; i++) {
if(target.equals(queue[i])){
index = i;
break;
}
}
//保证队列中有这样的位置点
if(index == -1){
return false;
}
//特殊情况,删除的是最后一个元素
if(size-1 == index){
queue[--size] = null;
return true;
}
//正常情况下
else {
queue[index] = null;
adjustDown(index, queue[size - 1]);
//特殊情况
if (queue[index] == queue[size - 1]) {
adjustDown(index, queue[size - 1]);
}
queue[--size] = null;
return true;
}
}
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < size; i++) {
stringBuilder.append(queue[i] +" ");
}
return stringBuilder.toString();
}
public static void main(String[] args) {
MyPriorityQueue<Integer> queue = new MyPriorityQueue<>();
queue.add(3);
queue.add(5);
queue.add(7);
queue.add(2);
queue.add(4);
queue.add(1);
System.out.println(queue.toString());
queue.remove();
System.out.println(queue.toString());
queue.removeAt(5);
System.out.println(queue.toString());
}
}
测试:
推荐阅读
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
深入理解Java优先级队列PriorityQueue的用法与实战解析
-
深入理解PriorityQueue(优先级队列):工作机制与内部构造解析