前言
优先级队列是在队列的基础上，每个元素都带有一个优先级，可以实现按照优先级高低进行存储和访问。 Java 提供了许多实现优先级队列的方法，例如使用堆来实现。在本篇博客中，我将介绍 Java 实现优先级队列实现的具体方法，以及如何使用它来解决实际问题。
一、优先级队列的概念
优先级队列是一种特殊的队列数据结构，它可以根据元素的优先级进行排序，并且在队列操作中优先考虑元素优先级高的元素。与普通队列不同的是，当有新元素加入队列时，队列会自动将其插入到适当的位置，而不是排在队尾。当执行出队操作时，队列会先返回队列中优先级最高的元素，而不是最先加入的元素。优先级队列常常用于任务调度、事件处理等场景，也可以用来解决各种排序问题。------>通俗点来说就是优先级队列也是一个队列，只不过出队列时是出当前队列中最小的那个，因为在队列内部就已经从小到大排序排好了，直接出就完事儿了，但是库函数的优先
二、优先级队列的实现（ Java 实现）
我们自己实现优先级队列的话那方法就多了，只要你是让最小的先出来就行，比如快排啊，冒泡排序啊，堆排啊……等等都可以做到，但是这边考虑时间复杂度，优先使用堆排序，在数据足够多的情况下，堆排的时间复杂度最小，下面是我们要实现的所有方法，大家也可以先试着思考一下，再接着看博客会比较容易吸收，代码如下：
public class PriorityQueue {
private int[] elem;// 建立一个线式堆
private int usedSize;// 堆里实际的元素
/* 构造方法 */
public PriorityQueue() {
}
/* 初始化成小根堆 */
public void createHeap(int[] array) {
}
/* 入队列，但还是要保持小根堆 */
public void push(int val) {
}
/* 出队列，但仍然要保持小根堆 */
public int pollHeap() {
}
/* 获取堆顶元素但不删除 */
public int peekHeap() {
}
/* 将元素向上调整 */
private void shiftUp(int child) {
}
/* 将元素向下调整 */
private void shiftDown(int parent,int end) {
}
}2.1、构造方法和peekHeap
如上代码，你们觉得哪个代码最简单呢？一眼看过去，是不是就是构造方法和peekHeap方法最简单呀，🆗，为了不一开始就打击我们的自信心，我们得挑点简单的试试手，那就写构造函数和peekHeap方法吧，代码实现如下：
/* 构造方法 */
public PriorityQueue() {
this.elem = new int[10];
this.usedSize = 0;
}
/* 出队列但不删除 */
public int peekHeap() {
// 判断数组里面是否存在数据
if (this.usedSize == 0) {
System.out.println("真的一滴也没有了");
return -1;
}
return this.elem[0];
}如上，我们就实现了构造方法和peekHeap方法，再接着看向下调整方法，我们画一个草图，如下：
2.2、向下调整
如上，这是一颗二叉树，向下调整，故名思意，意思就是将该父亲节点的数据如果比孩子节点大，就选出两个孩子中最小的那个，然后进行交换，直到比孩子小，等于孩子，或者已经到叶子节点了的时候，就不再进行交换，那如何确定是不是到了叶子节点呢？auv，我们不是定义了一个usedSize记录节点个数嘛，等于或者大于usedSize不就是到了叶子节点了？理论成立，下面来看代码实现：
private void shiftDown(int parent,int end) {
if (this.usedSize == 0) {
System.out.println("真的一滴也没有了");
return;
}
int child = ((parent * 2) + 1);
while (child < end) {
// 找出最小的那个孩子节点
if (((child + 1) < end) &&(this.elem[child] > this.elem[child + 1])) {
child++;
}
// 如果父亲节点比孩子节点大，那就交换
if (this.elem[parent] > this.elem[child]) {
int tmp = this.elem[parent];
this.elem[parent] = this.elem[child];
this.elem[child] = tmp;
}
// 把孩子节点的下标给父亲节点，然后孩子继续迭代往后走
// 直到孩子节点大于最大节点的下标才停下来
parent = child;
child = (parent * 2) + 1;
}
}如上就写完了一个向下调整，紧接着我们来看向上调整
2.3、向上调整
首先还是得想好思路，向上调整一般在插入数据的时候使用，这时数据除了插入进来的值，其他的数据是有序的，向上调整的意思不就是：假如孩子节点的值大于父亲节点，那就交换，再想一下循环出口，循环出口不就是当孩子节点小于或等于0时，就说明已经调整完了吗？但是，因为我们数据本来就是有序的还多了一个出口，那就是当父亲节点的值小于或等于孩子的值时，说明已经调完了，因为我们其他数据都有序了，那就剩这个插入进来的数据，只要这个插入进来的数据有序了，那我们所有数据不都有序了吗？如果没有走到else，那就把父亲节点的值给孩子，父亲迭代往后走，思路成立，代码实现如下：
private void shiftUp(int child) {
if (this.usedSize == 0) {
System.out.println("真的一滴也没有了");
return;
}
int parent = (child - 1) / 2;
// 当孩子节点下标为0时，证明已经调整完毕
while (child > 0) {
if (this.elem[parent] > this.elem[child]) {
int tmp = this.elem[parent];
this.elem[parent] = this.elem[child];
this.elem[child] = tmp;
}
else {
// 说明已经调整完毕
break;
}
child = parent;
parent = (child - 1) / 2;
}
}那向上调整和向下调整都写完了，我们该如何使用呢？我先透露一点，向上调整一般用在插入代码上，向下调整一般用在创建堆上，这样说就明白了吧？我们先来看比较简单的插入方法，也就是push方法。
2.4、入队列
老规矩，先检查一波扩容，然后再将新元素放到队尾，再调用向上调整把整个队列弄成小根堆，思路成立，代码实现如下：
public void push(int val) {
// 检查是否满了？是否需要扩容？
if (this.usedSize == this.elem.length) {
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
// 将新元素插入队尾
elem[this.usedSize++] = val;
// 再调用向上调整调整成小根堆
shiftUp(this.uusedSize - 1);
}2.5、出队列
出队列的思路是把队头元素和队尾元素交换，因为队尾元素最好出，如果出队头元素，那又要重新排序，出队尾元素的话，时间复杂度会小很多，思路成立，下面是代码实现：
public int pollHeap() {
if (this.usedSize == 0) {
System.out.println("真的一滴都没有了");
return -1;
}
// 交换
int ret = this.elem[0];
this.elem[0] = this.elem[this.usedSize - 1];
this.elem[--this.usedSize] = 0;
// 详细调整
shiftDown(0, this.usedSize);
return ret;
}2.6、初始化成小根堆队列
来到了所有方法里面比较难的方法了->初始化成小根堆，具体为什么难，马上来跟你解释，首先我们先思考，例如下面这个堆，是个无序的堆，如下：
先想好，我们想下调整，是要从最开始的那颗树->6-3-5开始，还是从最后那颗树->5-3开始呢？答案肯定是从最后一棵树开始呀，因为只有下面的树成小根堆了，那上面的才好调，给你假设一下从最开始那课树调整，假如6-3-5调完了了，假如5下面的3这时是1，那是不是1才是最小的呀，你上面的都调完了，那我这个1怎么办？是不是就上不去了呢？所以还得从最后的树开始调，然后每次调整的父节点的下标都不一样，也要一个循环，一直减1，直到父节点小于0才停下来，思路代码实现如下：
public void createHeap(int[] array) {
if (array.length == 0) {
return;
}
for (int i = 0; i < array.length; i++) {
this.elem[i] = array[i];
this.usedSize++;
}
for (int parent = ((usedSize - 1 - 1) / 2); parent >= 0; parent--) {
shiftDown(parent, this.usedSize);
}
}到这里，所有方法就写完了，我们来试着跑一下代码吧，如下：
先看在没有进入初始化方法之前，咱们的数据是如上这样的，再走一步，咱数据就变成这样了，如下：
怎么样？是不是就变成了一个小根堆呢？这么看你肯定看不出来，那如下这样呢？
这回总看出来了吧？我们再来试试其他的方法，运行结果如下：
三、总结
优先级队列是一种非常实用的数据结构，它能够以高效地方式处理特定问题。在 Java 中，我们可以使用PriorityQueue实现优先级队列，它使用堆排序算法来保证元素的优先级按照预期排序，同时提供了多种方法来往队列中插入、查询和删除元素。而且，PriorityQueue能够很好地应用于很多算法和数据解决方案的实现中，例如Dijkstra算法、Huffman编码等。总之，学习和熟悉优先级队列的实现和使用，对于提高编程能力和解决实际问题都是有很大好处的。
四、结语
在学习和实现优先级队列的过程中，我们会经历很多困难和挑战。但是只要持之以恒，耐心学习和不断尝试，我们就可以逐步掌握优先级队列的实现和使用技巧。同时，我们也应该坚信，无论学习什么，都需要不断地跨出自己的舒适区，才能不断提升自己的能力和技能。因此，让我们一起勇敢地面对挑战，迈出坚实的步伐，去实现我们的理想和目标！>
