优先级队列：PriorityQueue常用接口+构造+方法+源码分析+OJ练习

优先级队列：PriorityQueue常用接口+构造+方法+源码分析+OJ练习"/>

优先级队列：PriorityQueue常用接口+构造+方法+源码分析+OJ练习

文章目录

• PriorityQueue常用接口
• • 一.PriorityQueue 的特性
  • 二.PriorityQueue常用接口介绍
  • • 1.优先级队列的构造
    • 2.插入/删除/获取优先级最高的元素
    • 3.PriorityQueue的扩容方式：

PriorityQueue常用接口

一.PriorityQueue 的特性

• 1.Java集合框架中提供了 **PriorityQueue **和 **PriorityBlockingQueue **两种类型的优先级队列
• 2.PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

PriorityQueue底层由堆实现，堆由数组构造

import java.util.PriorityQueue;   
public static void main(String[] args) {PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();//直接实例化对象Queue<Integer> priorityQueue2 = new PriorityQueue<>();//默认是小根堆//用接口来调用}

• 3.使用时必须导入PriorityQueue所在的包
• 4.PriorityQueue中放置的元素，必须要能够比较大小，否则会抛出类型转换ClassCastException异常

        priorityQueue2.offer(new Student(12));priorityQueue2.offer(new Student(32));//ClassCastException,没有指定比较的元素，对象本身无法比较

1. PriorityQueue的offer方法，用的是向上调整，siftUp里面，用到了Comparator和Comparable方法
2. 要比较大小就要先实现Comparator和Comparable

• 5.不能插入null对象，否则会抛出空指针异常NullPointerException
• 6.内部会自动扩容
• 7.插入和删除元素的时间复杂度为 O ( log₂N )
• 8.PriorityQueue底层使用了堆的数据结构，默认是小根堆

二.PriorityQueue常用接口介绍

1.优先级队列的构造

• PriorityQueue() 不带参数的构造方法

创建一个空的优先级队列

调用无参构造器，初始容量默认为11，默认没有构造器

• PriorityQueue(int initialCapacity)

默认没有构造器

创建一个初始容量为initialCapacity的优先级队列，initialCapacity不能小于1，否则会抛IllegalArgumentException异常

• PriorityQueue(Collection<?extends E> c)

用一个集合来创建优先级队列

• PriorityQueue队列是小堆，如果需要大堆需要提供比较器

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可

2.插入/删除/获取优先级最高的元素

3.PriorityQueue的扩容方式：

1.如果容量小于64时，是按照oldCapacity的2倍方式扩容

2.如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的

3.如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

点击移步博客主页，欢迎光临~