Java-数据结构-优先级队列(堆的使用)
在学习优先级队列的使用之前，大家最好先学习下这篇文章：Java-数据结构-优先级队列(堆)-CSDN博客
以便更好的理解优先级队列是什么，以及(堆)的底层究竟如何运作。
一、优先级队列
在我们之前学习的队列中，仅仅按照入队的先后顺序来进行排序，并没有特殊的优先级，这样的情况就像是一家正常运作的医院中，病人们在病人窗口先后排序：
而在有些情况下，我们希望数据能够拥有一定的优先级，使我们每次取到的第一个元素都应该是当前所有数据中，优先级最高的那一个，这就像是繁忙的医院中，决定抢先医治病情严重，生命垂危的人：
而为了实现这种常规队列无法实现的要求，我们就引入了一个新的数据结构：优先级队列
① 优先级队列的特性
Java的集合框架中给出了两种类型的优先级队列，它们分别是：
"PriorityQueue"和"PriorityBlockingQueue"
两者的区别在于：前者线性不安全，后者线性安全，但相应的，后者效率必定不如前者高。
📚 PriorityQueue：
📕 适用于单线程环境，因为不需要处理线程同步，所以性能更高。
📕 适合单线程或手动管理线程同步的场景。
📚 PriorityBlockingQueue：
📕 适用于多线程环境，但线程同步会带来额外开销。
📕 适合多线程并发场景，能够简化线程安全的手动管理。
综上所述，两者的使用还需要看具体场景的需要，而由于我们刚刚接触优先级队列，所以这次就先为大家讲解"PriorityQueue"~
📖 优先级队列(PriorityQueue)的特性：
📕 在优先级队列中放置的元素必须是能够比较大小的，如果向优先级队列中放置无法比较大小的元素，则会抛出异常：
📕 优先级队列中不能存放null：
📕 PriorityQueue的内部会自动扩容
📕 PriorityQueue插入元素和删除元素的时间复杂度都为O(log n)
📕 PriorityQueue的底层使用的是堆，并且默认是小根堆
② 优先级队列的构造
📚 优先级队列的构造方法，常用的有以下几种：
📕 PriorityQueue()
优先级队列的空参构造，创建一个空的优先级队列：
通过这种方式去构造优先级队列，其默认的大小为11：
📕 PriorityQueue(int initialCapacity)
优先级队列的带参构造，创建一个初始容量为"initialCapacity"的优先级队列：
📕 PriorityQueue(Collection <？extend E>c)
用一个集合来创建优先级队列
而在上面我们所提到的一些问题，在这里我们也可以相应的去解决一下：
📕 在优先级队列中放置的元素必须是能够比较大小的：
比如有些时候，我们想要创建一个学生类，并且想要按照学生的学号来判定优先级(学号越小，优先级越高)并存入优先级队列中，直接将学生类存入PriorityQueue中是断然不可以的，因为直接将学生类存入优先级队列中，学生类的比较方法没有重写，所以算是无法排序的元素。相应的也就会报错。
那么想要解决这个问题也是很简单，我们只需要重写相应的排序方法即可：
为了防止有些小伙伴没有看上一篇博客，而是直接学习这篇博客，所以这边我们再强调一下，需要注意的是，PriorityQueue底层是堆，所以并不是从头到尾都是线性按照大小关系排序的，而是通过一颗树，并且每棵子树的根节点优先级都高于它的两个子结点，形如：
📕 PriorityQueue的底层使用的是堆，并且默认是小根堆：
对于这种情况，其实就更好解决了，我们同样需要重写一个比较方法：
③ 优先级队列的方法
以下仅列举一些常用的方法，其余内置的较为细致的方法，大家可以打开编译器自行阅读理解~
📖 offer方法 (插入元素)
📕 在队列中放入一个元素，如果放入成功则返回true，如果放入失败(满)则返回false；(但PriorityQueue是基于堆的动态扩容实现，不会满，因此总是返回 true)
与 offer 作用基本相同的方法还有一个我们熟知的 add，两者基本没有什么区别，两者唯一的区别就是(add在满时会直接抛出异常，而不是像offer一样优雅的返回false)
📖 peek方法 (获取优先级最高的元素)
📕 一般情况下，我们使用优先级队列的目的就是为了取出指定个数，优先级最高的元素。所以这个方法也是非常重要的，在之前我们学习中也已经见过，所以这里就不过多赘述了
📖 poll方法 (获取并移除优先级最高的元素)
📕 与上述方法基本一致~不多解释
📖 size方法 (获取有效元素个数)
📖 clear方法 (清空队列)
📖 isEmpty方法 (返回是(true)否(false)为空)
二、堆的应用
① 堆排序
我们使用堆可以实现很多功能，比如我们时常使用的排序中，就有可以用堆实现的排序：堆排序
具体思路还是比较简单的，我们知道堆的第一个元素是"优先级最高"的元素，那么如果我们使用大根堆，不断将堆顶的元素放到最后并删除(不是真删除，只是后续计算中不再移动这个元素)，这样就能够做到最大的元素在最后，也就是得到一个升序排列的一段数据~
⭐ 图示：
📖 代码示例(1.PriorityQueue)：
public static void HeapSort(int[] arr){
PriorityQueue<Integer> queue = new PriorityQueue<>(new ImpCmp());
for (int i = 0; i < arr.length; i++) {
queue.add(arr[i]);
}
for(int i = 0;i < arr.length;i++) {
arr[i] = queue.poll();
}
}
📖 代码示例(2.模拟实现)：
public static void heapSort(int[] array){
//构造一个大根堆
createHeap(array);
int len = array.length;
for(int i = len - 1;i > 0;i--){
//将array[0]放到最后(最大的数放到最后)
swap(array,0,i);
//向下调整,再次变成大根堆(堆到后面的大数不再调整)
siftDown(array,0,i);
}
}
public static void createHeap(int[] array){
int index = array.length;
//从最后一个父结点开始,依次将父结点向前进行向下调整
for(int parent = (index - 1 - 1) / 2;parent >= 0;parent--){
siftDown(array,parent,index);
}
}
public static void siftDown(int[] array,int parent,int len){
int child = 2 * parent + 1;
while(child < len){
if(child + 1 < len && array[child + 1] > array[child]){
child = child + 1;
}
if(array[child] > array[parent]){
swap(array,child,parent);
parent = child;
child = parent * 2 + 1;
}else {
break;
}
}
}
private static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
② Top-k问题
对于这题得解法，就有很多种使用堆来解决的方法~
📕 法1(1). 模拟小根堆,排序取前k个元素
📖 代码示例：
class Solution {
public static int[] smallestK(int[] array,int k){
createHeap(array);
int len = array.length;
for(int i = len - 1;i > 0;i--){
swap(array,0,i);
siftDown(array,0,i);
}
array = Arrays.copyOf(array,k);
return array;
}
public static void createHeap(int[] array){
int len = array.length;
int parent = (len - 1 - 1) / 2;
for(int i = parent;i >= 0;i--){
siftDown(array,i,len);
}
}
public static void siftDown(int[] array,int parent,int end){
int child = parent * 2 + 1;
while(child < end){
if(child + 1 < end && array[child] < array[child + 1]){
child++;
}
if(array[child] > array[parent]){
swap(array,child,parent);
parent = child;
child = parent * 2 + 1;
}else {
break;
}
}
}
public static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}📕 法1(2). 直接创建小根堆,排序取前k个元素
📖 代码示例：
class Solution {
public static int[] smallestK(int[] array, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < array.length; i++) {
queue.offer(array[i]);
}
int[] arr = new int[k];
for (int i = 0; i < k; i++) {
arr[i] = queue.poll();
}
return arr;
}
}📕 法2.重写compare,创建大小为k的大根堆
不断将小于堆顶的元素与堆顶交换,最后剩余的大根堆就是我们要找的前k个最小元素
📖 代码示例：
class IntBig implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
class Solution {
public static int[] smallestK(int[] array, int k) {
if (k == 0 || array.length == 0) {
return new int[0];
}
// 创建大根堆
PriorityQueue<Integer> queue = new PriorityQueue<>(new IntBig());
int[] arr = new int[k];
for (int i = 0; i < k; i++) {
queue.offer(array[i]);
}
for(int i = k;i < array.length;i++){
if(array[i] < queue.peek()){
queue.poll();
queue.offer(array[i]);
}
}
for (int i = k - 1; i >= 0; i--) {
arr[i] = queue.poll();
}
return arr;
}
}📕 法3.Top-k方法
建立一个大根堆，通过给定的k，将数组前k个元素一一放进堆中，然后遍历剩余的元素，如果出现元素小于当前的堆顶元素，则将堆顶元素删除，并将这个小于堆顶元素的元素放入堆中(并重新排序)，直到将所有元素遍历完，最后得到的就是前k个最小元素。
📖 代码示例：
class IntBig implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
class Solution {
public int[] smallestK(int[] array, int k) {
int[] arr = new int[k];
if(k == 0){
return arr;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new IntBig());
for(int i = 0;i < k;i++){
queue.offer(array[i]);
}
for(int i = k;i < array.length;i++){
if(array[i] < queue.peek()){
queue.poll();
queue.offer(array[i]);
}
}
for(int i = k - 1;i >= 0;i--){
arr[i] = queue.poll();
}
return arr;
}
}这篇文章我们对"优先级队列"进行了进一步的了解，那么这篇文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦