行业知识
Java数据结构 | PriorityQueue详解
���录
一 、PriorityQueue
二、PriorityQueue常用方法介绍
三、 PriorityQueue源码剖析
四：应用：Top-K问题
一 、PriorityQueue
-
常用接口介绍
上文中我们介绍了优先级队列的模拟实现， Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，此处我们主要刨析和介绍PriorityQueue
关于PriorityQueue的使用要注意：
-
使用时必须导入PriorityQueue所在的包，即：
-
PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException*异常**
-
不能插入null对象，否则会抛出NullPointerException**
-
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
-
插入和删除元素的时间复杂度为
-
PriorityQueue底层使用了堆数据结构, (注意：此处大家可以不用管什么是堆，后文中有介绍)
-
PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素、
二、PriorityQueue常用方法介绍
-
构造方法
常用的三个构造方法如下：
public class TestDemo2 { public static void main(String args[]){// 创建一个空的优先级队列，底层容量默认为11 PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.offer(10); priorityQueue.offer(20); priorityQueue.offer(12); priorityQueue.offer(23); System.out.println(priorityQueue.poll()); System.out.println(priorityQueue.poll()); System.out.println(priorityQueue.poll()); System.out.println(priorityQueue.poll());// 创建一个指定初始容量的优先级队列，容量指定位100 PriorityQueue priorityQueue1 = new PriorityQueue(100);// 使用ArrayList对象来创建一个优先级队列的对象（只要实现Collection接口的,都可以存入） List list = new ArrayList(); list.add(10); list.add(20); list.add(32); PriorityQueue priorityQueue2 = new PriorityQueue(list); System.out.println(priorityQueue2.poll()); System.out.println(priorityQueue2.poll()); }}注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
三、 PriorityQueue源码剖析
-
使用Student对象来创建一个优先级队列的对象
当我们在priorityQueue中存放一个Student 对象时， 可以正常放入且不发生报错。
但是当我们存放两个Studnet对象时，程序报错，出现类型不兼容异常。
public class TestDemo2 {// 注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器 public static void main(String[] args) { PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.offer(new Student(10)); priorityQueue.offer(new Student(5)); } }前边学习抽象类和常用接口时，我们了解到Java中对于引用数据类型的比较或者排序，一般都要用到使用Comparable接口中的compareTo() 方法
此时我们可以实现Comparable接口，并且重写 compare()方法。
class Student implements Comparable{ public int age; public Student(int age) { this.age = age; } @Override public int compareTo(Student o) { return this.age - o.age; }}public class TestDemo2 {// 注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器 public static void main(String[] args) { PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.offer(new Student(10)); priorityQueue.offer(new Student(5)); }}经过调试我们可以发现，此时优先级队列中的两个元素已经按照小根堆的方式调整好了。
那么PriorityQueue是怎么对其中的引用数据类型进行调整的呢？
使用this引用指向了下边的方法，并传递参数。
当queue数组初始化完毕时， 需要向数组中存放元素，即进行 priorityQueue.offer(new Student(10));
存放第二个元素时，i = 1 , size = 2 ,则需要执行 siftUp(1 , e) ,对 元素进行向上调整为小根堆 。
向下调整的过程中，使用了我们所重写的compareTo()方法，然后判断e,key对应的age的值，进行交换，如果此处不需要交换，则直接将key放入queue[1] 中即可 ， 此时，小根堆调整完成
如果想要调整为大根堆的话，只需要修改Student类中的compareTo()方法即可
class Student implements Comparable{ public int age; public Student(int age) { this.age = age; } @Override public int compareTo(Student o) { return o.age - this.age; }}那么Integer类型的参数该如何修改为大根堆 呢？ ，Integer类型已经重写了compareTo方法，但是已经写***了，默认为小根堆的实现方式，无法修改源码，此时，我们就应该 构造Comparator 比较器来实现。
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可class IntCmp implements Comparator{ @Overridepublic int compare(Integer o1, Integer o2) { //return o2-o1; return o2.compareTo(o1); } }public class TestPriorityQueue { public static void main(String[] args) { PriorityQueue p = new PriorityQueue(new IntCmp()); p.offer(4); p.offer(3); p.offer(2); p.offer(1); p.offer(5); }}❗当传入比较器时，PriorityQueue会按照 比较器的方式进行 比较，与实现Comparable 接口的方法类似，此处不再赘述，元素进而被调整为大根堆。
✅另一种写法 ：
public class TestPriorityQueue { public static void main(String[] args) { //匿名内部类，这里有一个类，实现了Comparator 这个接口，并重写了compare这个方法 PriorityQueue p = new PriorityQueue(new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); }}PriorityQueue的扩容机制：
优先级队列的扩容说明：
-
如果容量小于64时，是按照约oldCapacity的2倍方式扩容的（2*OldCapacity+2）
-
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
-
如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容
四：应用-Top-K问题
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
-
用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
-
用剩余的**N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素**
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
在不使用Arrays.sorrt 的情况下，使用优先级队列，（忽略时间复杂度）可以这样写：
1 . 先将数组全部放入堆中，堆会自动调整为小根堆。
2 . 每次将堆顶元素弹出，堆调整之后，再继续弹出共k 个堆顶。
class Solution{ public int[] smallestK(int[] arr,int k){ PriorityQueue pr = new PriorityQueue(); for(int i = 0 ;i此时的时间复杂度为 O（ｎ＋ｋlog（ｎ）），那么如何调整可以使时间复杂度进一步优化呢？
１．先将这组数据中的前Ｋ个数据建立为大根堆
２. 从Ｋ＋１个元素开始，每次和堆顶元素进行比较，如果ｉ下标的元素小于堆顶元素，则进行出堆。
区别：1 . 没有整体建堆（大小为K的堆） 2. 遍历剩下n-k 个元素，每个元素与堆顶元素比较。
class Solution { public int[] smallestK(int[] arr, int k) { int[] vec = new int[k]; if (k == 0) { return vec; } //传入比较器，按照大根堆调整 PriorityQueue queue = new PriorityQueue(new Comparator() { public int compare(Integer num1, Integer num2) { return num2 - num1; } }); //存入K个 元素 for (int i = 0; i arr[i]) { queue.poll(); queue.offer(arr[i]); } } //将堆中元素存入数组中 for (int i = 0; i此时已经可以求出前K个最小的元素，且时间复杂度为Nlog(K)那么第K小的元素如何去求呢？步骤基本是相似的
１．先将这组数据中的前Ｋ个数据建立为大根堆
２. 从Ｋ＋１个元素开始，每次和堆顶元素进行比较，如果ｉ下标的元素小于堆顶元素，则进行出堆。
3 . 比较完成后直接弹出堆顶元素，即为第K小的元素。
到这里优先级队列部分的内容就结束了，欢迎点赞评论收藏。。
-
-
-
-
