【Java数据结构】优先级队列详解（二）
🔒文章目录：
1.❤️❤️前言~🥳🎉🎉🎉
2.PriorityQueue的特性
3.优先级队列的构造
4.如何控制优先级队列是小堆还是大堆
5.PriorityQueue的方法
6. PriorityQueue的自动扩容方式
7.top-k问题——最小k个数
8.堆排序
9.总结
1.❤️❤️前言~🥳🎉🎉🎉
Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。
如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。
当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！
加油，一起CHIN UP！💪💪
🔗个人主页：E绵绵的博客
📚所属专栏：1. JAVA知识点专栏
深入探索JAVA的核心概念与技术细节
2.JAVA题目练习
实战演练，巩固JAVA编程技能
3.c语言知识点专栏
揭示c语言的底层逻辑与高级特性
4.c语言题目练习
挑战自我，提升c语言编程能力
📘 持续更新中，敬请期待❤️❤️
2.PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
该图是priorityQueue的父类和接口，了解一下就行了。
关于PriorityQueue的使用要注意：
1. 使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常。这个等会会详细介绍。
3. 优先级队列不能插入null对象，否则会抛出NullPointerException（普通队列和栈都能插入null对象，优先级队列不行）
4. 没有容量限制，可以插入任意多个元素，其内部数组可以自动扩容.
5. PriorityQueue底层使用了堆数据结构
3.优先级队列的构造
👉无参构造法 底层数组默认容量是11
Queue<Integer> priorityQueue1 = new PriorityQueue<>();
👉整形数据作为参数, 设置化底层数组容量
Queue<Integer> priorityQueue2 = new PriorityQueue<>(10);
👉用一个集合来创建优先级队列，该集合中的数据全放到优先级队列中（创建后原本的顺序可能会改变，因为它是大根堆或小根堆）
PriorityQueue(Collection<? extends E> c)
这个构造函数接受的是一个Collection类型的参数，因此可以传入任何实现了Collection接口的类的对象。
并且因为该构造函数还使用了<? extends E>，它表示传递给构造函数的集合c中的<元素类型>必须是E或E的子类。
以下是实例：
Queue<Integer> queue=new ArrayDeque<>();queue.offer(8);queue.offer(7);queue.offer(9);PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(queue);System.out.println(priorityQueue.size());System.out.println(priorityQueue.peek());
4.如何控制优先级队列是小堆还是大堆
默认情况下，我们用以上三种构造方法创建的PriorityQueue队列是小堆，具体我们看源码。
当我们执行之前讲过的三种任意一种构造方法时，comparator都是null，所以在执行之后的操作必会执行类似的siftupComparable方法，该方法源码如下
由此可知当我们priorityqueue存储的是包装类如Integer时，其默认为小根堆。
而当我们用自定义类比较时，因为如上源码用了compareTo去比较，该方法是comparable类的方法，如果该自定义类没有实施comparable接口，重写compareTo方法去比较该类 ，则会出现异常报错。（包装类本身重写了compareTo方法）
以下是正确做法：
public class Test4 {public static void main(String[] args) {PriorityQueue<Method> priorityQueue=new PriorityQueue<>();priorityQueue.offer(new Method(4));priorityQueue.offer(new Method(8));priorityQueue.offer(new Method(9));System.out.println(priorityQueue.peek().size);}
}class Method implements Comparable<Method>{public int size;@Overridepublic int compareTo(Method o) {return o.size-this.size;}public Method(int size) {this.size = size;}} 
由结果可以发现创建了大根堆，这是因为重写的compareTo方法中this类的size如果大于o类的size，则返回负数。导致为大根堆（具体细节观察源码可以发现，这里不细讲）
所以我们发现了一个很重要的规律：对于重写的方法，如果前面的类大于后面的类（this一般看作前面的类），该方法返回出正数，则为小根堆。否则为大根堆。
除此之外这里还有第四种构造方法，也是最为重要的，这个需要我们自己创建一个比较类。
由该构造方法可知，我们要接收一个类且该类必须实施了comparator接口，该接口的泛型参数必须为E本身或者E的父类（E为priorityQueue创建出的对象的泛型参数）。
由上可知，在构造完后，comparator就不为null，所以执行siftupusingComparator方法，其源码如下：
此时内部我们就执行了compare方法，comparator接受的是我们之前创建的比较类，所以执行比较类中重写的compare方法，我们就能通过该方法去控制是大根堆还是小根堆 。
以下是正确做法：
（堆内部存储着包装类）
public class Test3 {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Int());priorityQueue.offer(4);priorityQueue.offer(8);priorityQueue.offer(9);System.out.println(priorityQueue.peek());}
}class Int implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}}
根据规律得出 o1如果大于o2，则返回负数，所以是大根堆，打印出9
（堆内部存储着自定义类）
public class Test5 {public static void main(String[] args) {PriorityQueue<Method1> priorityQueue=new PriorityQueue<>(new Meth());priorityQueue.offer(new Method1(4));priorityQueue.offer(new Method1(8));priorityQueue.offer(new Method1(9));System.out.println(priorityQueue.peek().size);}
}
class Method1 {public int size;public Method1(int size) {this.size = size;}
}
class Meth implements Comparator<Method1> {@Overridepublic int compare(Method1 o1, Method1 o2) {return o1.size-o2.size;}
}
根据规律得出 o1如果大于o2，则返回正数，所以是小根堆，打印出4.
现在来个总结：
1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法，控制其为大根堆或小根堆。当插入包装类时默认就是小根堆改变不了。
2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象或包装类对象时，可以提供一个比较器类，让该类实现 Comparator接口并覆写compare方法，从而控制该堆是大堆还是小堆。
5.PriorityQueue的方法
因为是优先级队列，所以它的这些方法名称自然跟普通队列一模一样，只是本质是不一样的。（对于这些本质我们在上一篇文章中模拟过了，了解的很清楚了就不多说了）
需要记住的是：
offer不能输入null进去，否则会报错。
当队列为空时，peek和poll都会返回null 。
public class Test2 {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();priorityQueue.offer(4);priorityQueue.offer(8);priorityQueue.offer(9);System.out.println(priorityQueue.peek());priorityQueue.poll();System.out.println(priorityQueue.size());System.out.println(priorityQueue.isEmpty());priorityQueue.clear();System.out.println(priorityQueue.isEmpty());}
}
6. PriorityQueue的自动扩容方式
这个只需了解就行，无需详细记住，知道它能自动扩容就ok了。
7.top-k问题——最小k个数
📌题目描述
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
📋题目思路
创建优先队列（PriorityQueue）：使用
PriorityQueue<Integer>，这是一个自调整大小的最小堆数据结构。堆的特性保证了插入元素时总是将当前最小的元素添加到队列顶部。遍历数组并插入优先队列：使用
for循环遍历输入数组arr，将每个元素arr[i]添加到priorityQueue中。由于优先队列自动维护最小值，所以每次添加都会替换队列顶部（也就是当前最小值）。构建结果数组：当遍历完整个输入数组后，
priorityQueue中应该包含了前k个最小元素。再次使用for循环，从priorityQueue中取出k个元素并放入新数组arr1。因为poll()方法会返回并移除队列中的最小元素，所以这里实际上是按顺序获取最小元素。返回结果：完成
arr1的构建后，返回这个包含前k小元素的数组。
⏳题目代码
class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();for (int i = 0; i <arr.length ; i++) {priorityQueue.offer(arr[i]);}int[] arr1=new int[k];for (int i = 0; i <k ; i++) {arr1[i] = priorityQueue.poll();}return arr1;} }
题目链接：最小k个数
8.堆排序
我们通过堆这种数据结构去排序数组 就叫堆排序。这里简单说一下，不过多牵扯，代码示 例如下：
public class Sort {public static void main(String[] args) {int[] arr={0,-3,6,9,65,12,43,4,36,21,-9};PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Int());for (int i = 0; i <arr.length ; i++) {priorityQueue.offer(arr[i]);}for (int i = 0; i <arr.length ; i++) {arr[i]= priorityQueue.poll();}System.out.println(Arrays.toString(arr));}}
这里我们用堆排序将数组从大往小排。对于上述代码大家应该都能看懂，就不多说了，看下对于堆的实际应用就行了。
9.总结
所以这篇文章我们就把堆（priorityqueue）的使用讲述清楚了，堆也就此完结了，花了两篇文章去讲解。之后将给大家带来排序的讲解。在此，我们诚挚地邀请各位大佬们为我们点赞、关注，并在评论区留下您宝贵的意见与建议。让我们共同学习，共同进步，为知识的海洋增添更多宝贵的财富！🎉🎉🎉❤️❤️💕💕🥳👏👏👏
