---

前言

我们之前学习过队列，它是遵循先进先出原则的数据结构，对应我们现实生活中的先到先得原则，比如排队时我们就可以使用队列的数据结构来模拟实现。但是，如果我们想优先操作队列中的某些数据，即让优先级高的元素先出队列，那么这种“普通的”先进先出队列就无法满足我们的需求。这时候就需要“优先级队列”来帮忙了

---

1. 优先级队列

1.1 概念

优先级队列（Priority Queue）是一种抽象数据类型，它类似于常规的队列或栈，但每个元素都有一个优先级。在优先级队列中，最小元素（或最大元素，根据实现）总是在队列的前端，并且最先被移除。它通常用于需要根据元素的重要性或紧急性进行排序的场景。比如：任务调度，网络数据传输，订单处理等等

---

1.2 特性

1. PriorityQueue 类是实现优先级队列的常用类，底层实现是堆，而堆一棵特殊的完全二叉树（下面我们会重点讲解堆）
2. 默认情况下，PriorityQueue 不允许插入重复的元素
3. PriorityQueue 不是线程安全的。如果需要在多线程环境中使用，我们可以使用 PriorityBlockingQueue，它是线程安全的优先级队列实现

---

2. 堆

2.1 概念

在逻辑结构上，堆是一棵完全二叉树，而在存储结构上，堆是通过一个一维数组来存储元素的。它把所有元素按完全二叉树的层序遍历顺序，存储在一个数组当中。并且在堆中，每个节点都必须满足以下两种属性之一：

小根堆（最小堆）：父节点的键值必须小于或等于其子节点的键值

大根堆（最大堆）：父节点的键值必须大于或等于其子节点的键值

---

2.2 存储方式

在上面我们提到了，“堆是通过一个一维数组来存储元素的”，而它的存储顺序就是按照完全二叉树的层序遍历来存储的，这样可以更高效的利用存储空间

因为使用数组存储堆可以方便地实现父节点到子节点的转换，所以我们可以给每一个节点记一个下标，通过下标来得到节点之间的父子关系：

我们规定根节点的下标为 0，设 i 为节点在数组中的下标，则有：

• 父节点的下标：(i - 1) / 2
• 左节点的下标： i * 2 + 1（如果得出来的数大于等于总的节点个数，则该节点没有左节点）
• 右节点的下标： i * 2 + 2（如果得出来的数大于等于总的节点个数，则该节点没有右节点）

下面是简单的对应关系图：

---

3. 堆的模拟实现

3.1 堆的创建

问题：把集合 {37，26，77，45，6，21，66，18，42} 创建成一个大根堆

思路：我们可以先把集合中的数据先按原始顺序排成一棵完全二叉树，接着再来调整，直至调整成为一个大根堆

那要怎么调整呢？很简单，我们回忆一下大根堆的特点：在每棵子树中，父节点始终大于子节点。顺着这个思路，我们可以得出方法：从最后一棵子树开始调整，拿根节点和两个子节点比大小，如果出现任一子节点大于根节点，就交换两者的位置，这个过程叫做“根节点的向下调整”；然后接着往前找子树，一样的套路继续调整，直至所有的父节点都大于子节点，最后调整结束，得到的就是大根堆了

干讲可能有点抽象，我们根据代码来辅助理解：

首先我们创建一个数组 elem，并设定初始容量为 10，再使用 usedSize 来记录实际容量；接着初始化数组，把要传进去的数组赋值进去

public class MyHeap {public int[] elem;public int usedSize;//构造方法public MyHeap() {this.elem = new int[10];}//初始化，把数组一个个赋值进去public void init(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}
}

现在我们就得到了一组原始数组，它是一棵待排序的二叉树，接着开始调整

    //把 elem 数组中的数据调整为大根堆//时间复杂度为 O(n)public void createHeap() {//parent 为待调整树的父节点位置for (int parent = (usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {shiftDown(parent, usedSize);}}//向下调整public void shiftDown(int parent, int end) {int child = 2 * parent + 1;//如果存在孩子节点，就进入循环while (child < end) {//判断最大的孩子是在左还是在右if (child + 1 < end && elem[child] < elem[child+1]) {child++;}//此时child一定是最大的孩子if (elem[child] > elem[parent]) {swap(child, parent);//交换完后再往下走parent = child;child = 2 * parent + 1;}else {//说明不需要调整，直接跳出break;}}}//交换位置public void swap(int i, int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}

通过这么一套操作，我们就能得到大根堆，最后打印出来就是顺序就是正确的

注意：在调整以 parent 为根的树时，要保证它的左右子树都已经是堆了才能向下调整，这也是我们从最后一棵子树开始调整的原因

---

时间复杂度：在最坏的情况中，我们需要对每个元素进行下沉操作，下沉操作的时间复杂度是 O(log n)，因为堆是一个完全二叉树，其高度是 log(n)。但总的下沉次数是 n，因此平均到每个节点上的时间复杂度就是常数时间。这导致总的时间复杂度是 O(n)

---

3.2 堆的插入

将元素插入到堆中，插入后依然要满足堆的性质

实现思路：

1. 判断数组容量是否满了，满的话要扩容
2. 把要插入的数据放在最后面，记得让 usedSize++，接着向上调整 (siftUp)
3. 直到满足堆的性质

---

在原先的大根堆中插入 54，要求最后的结果还是大根堆

    //堆的插入public void offer(int val) {if (isFull()) {//满了就扩容elem = Arrays.copyOf(elem,2 * elem.length);}//在最后一个位置添加欲插入数据elem[usedSize] = val;usedSize++;//向上调整shiftUp(usedSize - 1);}//向上调整public void shiftUp(int child) {//先找到父节点int parent = (child - 1) / 2;//如果存在父节点，就进入循环while (parent >= 0) {if (elem[child] > elem[parent]) {swap(child, parent);//交换后，继续往上，看是否需要调整child = parent;parent = (child - 1) / 2;} else {break;}}}//判满public boolean isFull() {return usedSize == elem.length;}

---

3.3 堆的删除

因为堆的特性，所以堆的删除我们通常指的是堆顶元素的删除，也就是说删除的是堆中最大（或者最小）的元素

实现思路：目的是为了尽可能的减少堆中元素的移动，保持堆的特性，因此我们可以采用逻辑删除

1. 让堆顶元素和堆中最后一个元素交换
2. 让 usedSize 减一（逻辑删除）
3. 最后调整堆顶元素，向下调整

---

删除堆中的堆顶元素，并要求删除后依然是一个大根堆

    //弹出第一个数字public int poll() {//先判断堆是不是空的if (isEmpty()) {return -1;}int old = elem[0];//记录下第一个数//把第一个和最后一个交换swap(0,usedSize - 1);//再排成大根堆usedSize--;//把最后一个数覆盖掉//第一个数向下调整，传入自己位置和堆的实际容量shiftDown(0,usedSize);//返回删除的元素return old;}public boolean isEmpty() {return usedSize == 0;}

除了 poll( ) 弹出，我们也可以来实现 peek( )，即瞥一眼堆顶元素，这个就很简单了

    //瞥一眼第一个元素public int peek() {//先判断堆是不是空的if (isEmpty()) {return -1;}return elem[0];}

---

4. PriorityQueue

4.1 注意事项

在使用之前，记得导包

import java.util.PriorityQueue;

接下来，我们来详细讲解使用时的一些注意点：

1. 在 PriorityQueue 中放置的元素必须是可比较的，若插入无法比较大小的元素，就回抛出 ClassCastException 类型转换异常
2. 在使用优先队列之前，应检查队列是否为空，避免在空队列上执行删除操作导致错误
3. 不能插入 null，否则会抛出 NullPointerException 空指针异常
4. PriorityQueue 默认情况下是小堆，若想建成的是大堆，则需要在构造时传入比较器
5. PriorityQueue 不是线程安全的。如果需要在多线程环境中使用，我们可以使用 PriorityBlockingQueue，它是线程安全的优先级队列实现

---

4.2 构造器介绍

1. 默认构造方法：创建一个空的优先队列，默认容量为 11

   public PriorityQueue() 
   

2. 带初始容量的构造方法：可以指定初始容量

   public PriorityQueue(int initialCapacity)
   

3. 带初始集合的构造方法：可以指定集合中的元素来初始化（实现了 Collection 接口的就可以接收，该集合的类型是包含 E 类型或其任何子类型的对象）

   public PriorityQueue(Collection<? extends E> c)
   

4. 带比较器的构造方法：可以使用指定的比较器来初始化（比较器决定了元素的排序方式）

   public PriorityQueue(Comparator<? super E> comparator)
   

5. 带初始集合和比较器的构造方法：可以使用指定集合中的元素和比较器来初始化

   public PriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator)
   

在这里我们重点演示一下带比较器的构造方法：

class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); //调换了原来的顺序}
}
public class Test {public static void main(String[] args) {//不传入比较器PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();priorityQueue1.offer(24);priorityQueue1.offer(52);priorityQueue1.offer(14);priorityQueue1.offer(37);System.out.println("小根堆：" + priorityQueue1);//传入比较器PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new IntCmp());priorityQueue2.offer(24);priorityQueue2.offer(52);priorityQueue2.offer(14);priorityQueue2.offer(37);System.out.println("大根堆：" + priorityQueue2);}
}    

运行结果如下：

---

4.3 常用方法介绍

方法	描述
boolean offer(E e)	将指定元素添加到此队列中
E peek( )	返回队列头部的元素但不移除它。如果队列为空，则返回 null
E poll( )	移除此队列头部的元素。如果队列为空，则返回 null
int size( )	返回队列中的元素数量
boolean remove(Object o)	从队列中移除指定的元素，移除成功返回 true，否则返回 false
void clear( )	移除队列中的所有元素
boolean isEmpty( )	如果队列为空，则返回 true

以上都是 PriorityQueue 的常用方法，有需要的话可以去该网址查询： PriorityQueue 的官方文档

---

5. 经典题型

Top-K 问题：求数据集合中前 K 个大（或者小）的元素

我们可以想想要怎么解决这个问题？最“朴素”的方法，当然是直接把数据集合排序，这样取到前 K 个大（或者小）的元素当然很简单

但是如果此时的数据量非常大，用排序法的时间复杂度一定不小，因此我们可以使用堆来求，那要怎么求呢？

---

力扣：最小K个数

---

思路：问题要求我们找到前 k 个小的元素，“前 K 个”的意思就是我们不需要给所有数排序，只要把数据集合中的前 k 个小的元素就行

题目要求取出数据中前 k 个小的元素，我们就得建大堆（有点反直觉），把前 k 个数据先建成一个大堆，接着将剩余的 N - k 个元素依次和堆顶元素比较，比堆顶元素小就换，比完后堆中剩余的 k 个元素就是题目所要求的数

class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); }
}class Solution {public int[] smallestK(int[] arr, int k) {//建大堆，只放前k个数PriorityQueue<Integer> minK = new PriorityQueue<>(new IntCmp());for (int i = 0; i < k; i++) {minK.offer(arr[i]);}//比较大小，若比堆顶元素小就放进去for (int i = k; i < arr.length; i++) {if(minK.size() != 0 && arr[i] < minK.peek()) {minK.poll();minK.offer(arr[i]);}}//返回int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = minK.poll();}return ret;}
}

当然，有很多其他更好的解法，博主在这只是提供一个简单的思路

---

6. 结语

今天我们介绍了优先级队列，重点掌握它的特性，还有堆的概念以及模拟实现，明白怎么使用 PriorityQueue 的常用方法，还有 Top—K 问题，也是非常经典~

希望大家能够喜欢本篇博客，有总结不到位的地方还请多多谅解。若有纰漏，希望大佬们能够在私信或评论区指正，博主会及时改正，共同进步！