阅读量:0
前言：优先级队列（Priority Queue）是一种抽象数据类型，其中每个元素都关联有一个优先级，元素按照优先级顺序进行处理。
✨✨✨这里是秋刀鱼不做梦的BLOG
✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客
先让我们看一下本文大致的讲解内容：
目录
（2）插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空
1.优先队列的初识
（1）优先级队列的定义
在开始学习Java中优先级队列的使用之前，先让我们了解一下什么是Java中的优先级队列（PriorityQueue）：
优先级队列（Priority Queue）是一种抽象数据类型，其中每个元素都关联有一个优先级，元素按照优先级顺序进行处理。与标准队列不同，优先级队列中的元素处理顺序并非按插入顺序，而是按照优先级高低来决定。
如果读者看了优先级队列的定义之后还是不是太理解什么是优先级队列，那么现在我们使用一个日常生活中的例子来帮助你理解：
——例如在医院急诊室，虽然你可能先到，但是医生会根据病人的病情严重程度来决定治疗顺序。病情严重的病人（例如，心脏病发作的病人）会被优先治疗，而病情较轻的病人（例如，轻微的感冒）会被安排在后面。
这样我相信读者就对优先级队列有了初步的认识了！！！
（2）PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队，而对于PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，而本文我们主要介绍是PriorityQueue。
其在Java集合框架中的关系图为：
关于PriorityQueue的使用要注意：
1. 使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常；
3. 不能插入null对象，否则会抛出NullPointerException；
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容；
5. 插入和删除元素的时间复杂度为O（logN）；
6. PriorityQueue底层使用了堆数据结构；
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素；
至此，我们通过上述对Java中的优先级队列的简单讲述，我们就大致的了解了什么是Java中的优先级队列了！
2.优先级队列的模拟实现
在了解完了什么是Java中的优先级队列之后，现在让我们想想看如何去自我实现一个Java中的优先级队列呢？
——这里我们已经在每处加上了注释，希望读者可以跟随着注释进行理解代码：
package Demo1; import java.util.Arrays; // 堆的自我实现 - 创建堆 + 插入数据 + 删除数据 + 返回堆顶元素 + 判断是否为空 public class MyPriorityQueue { public int[] elem; // 存储堆元素的数组 public int useSize; // 当前堆中元素的个数 // 初始化堆 public MyPriorityQueue(int[] array) { elem = new int[11]; // 初始化堆的容量 for (int i = 0; i < array.length; i++) { elem[i] = array[i]; // 将传入的数组元素放入堆中 useSize++; // 更新堆中元素的个数 } makeBigHeap(array, useSize); // 创建大根堆 } // 整体创建堆 public void makeBigHeap(int[] array, int useSize) { // 从最后一个非叶子节点开始向上调整 for (int parent = (useSize - 1 - 1) / 2; parent >= 0; parent--) { shiftDown(parent, useSize); // 对每个非叶子节点进行下沉操作 } } // 下沉操作 private void shiftDown(int root, int useSize) { int child = 2 * root + 1; // 左子节点索引 while (child < useSize) { // 遍历堆 // 如果右子节点存在且右子节点的值大于左子节点的值，选择右子节点 if (child + 1 < useSize && elem[child] < elem[child + 1]) { child++; } // 如果当前节点的值小于子节点的值，交换它们 if (elem[root] < elem[child]) { swap(root, child); root = child; // 更新根节点为被交换的子节点 child = 2 * root + 1; // 更新左子节点的索引 } else { break; // 如果根节点的值不小于任何子节点，退出循环 } } } // 在堆中插入元素 private boolean isFull() { return useSize == elem.length; // 判断堆是否满了 } public void offer(int val) { if (isFull()) { elem = Arrays.copyOf(elem, 2 * elem.length); // 扩容 } elem[useSize] = val; // 将新元素放入堆的末尾 shiftUp(useSize); // 上浮操作调整堆 useSize++; // 更新堆中元素的个数 } // 上浮操作 private void shiftUp(int child) { int parent = (child - 1) / 2; // 计算父节点的索引 while (parent >= 0) { // 如果当前节点的值大于父节点的值，交换它们 if (elem[parent] < elem[child]) { swap(parent, child); child = parent; // 更新子节点为被交换的父节点 parent = (child - 1) / 2; // 更新父节点的索引 } else { break; // 如果当前节点的值不大于父节点的值，退出循环 } } } // 删除堆中元素 public void poll() { if (isEmpty()) { throw new RuntimeException("堆中元素为空！"); // 如果堆为空，抛出异常 } swap(0, useSize - 1); // 将堆顶元素与最后一个元素交换 useSize--; // 更新堆中元素的个数 shiftDown(0, useSize); // 对堆顶元素进行下沉操作 } // 获取堆顶元素 public int peek() { if (isEmpty()) { throw new RuntimeException("堆中元素为空！"); // 如果堆为空，抛出异常 } return elem[0]; // 返回堆顶元素 } // 判断堆是否为空 private boolean isEmpty() { return useSize == 0; // 如果堆中没有元素，返回 true } // 交换数组中的两个元素 private void swap(int pos1, int pos2) { int temp = elem[pos1]; elem[pos1] = elem[pos2]; elem[pos2] = temp; } } public class Test { public static void main(String[] args) { // 初始化一个整数数组 int[] array = {1, 4, 2, 7, 9, 10, 5, 6, 8, 3}; // 创建一个优先级队列实例 MyPriorityQueue myPriorityQueue = new MyPriorityQueue(array); // 向优先级队列中插入多个元素 myPriorityQueue.offer(5); myPriorityQueue.offer(3); myPriorityQueue.offer(8); myPriorityQueue.offer(1); // 打印堆顶元素 System.out.println(myPriorityQueue.peek()); // 删除堆顶元素 myPriorityQueue.poll(); // 判断堆是否为空，并打印结果（注意这里原代码并未打印结果，需手动添加打印语句） System.out.println("堆是否为空: " + myPriorityQueue.isEmpty()); } } 从中我们可以看到我们使用堆这个数据结果来自我实现了从 - 创建堆 - 插入数据 - 删除数据 - 返回堆顶元素 - 判断是否为空等优先队列中的操作。至此我们完成了自我实现Java中的优先级队列（PriorityQueue）。
如果对于堆这种数据结构不了解的读者，可以阅读---------->Java中的Heap（堆）（如果想知道Java中有关堆的知识点，那么只看这一篇就足够了！）-CSDN博客
3.优先级队列中常用API
通过上面的学习，我们已经了解了什么是Java中的优先级队列，并且自我实现了优先级队列，现在让我们看看Java中内置的优先级队列该如何使用吧！
（1）创建优先级队列
PriorityQueue类提供了多种构造方法，允许创建不同配置的优先级队列。
| 构造器 | 功能 |
|---|---|
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则IllegalArgumentException异常 |
| PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
例子：
import java.util.PriorityQueue; public class PriorityQueueDemo { public static void main(String[] args) { // 默认初始容量的优先级队列 PriorityQueue<Integer> pq = new PriorityQueue<>(); // 指定初始容量的优先级队列 PriorityQueue<Integer> pqWithCapacity = new PriorityQueue<>(20); // 使用比较器的优先级队列 PriorityQueue<Integer> pqWithComparator = new PriorityQueue<>(new CustomComparator()); } } ——这样我们就会常见Java中的优先级队列了！
在了解了如何创建一个优先级队列之后，接下来让我们看一下如何去操作这个创建的优先级队列。
（2）插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空
| 函数名 | 功能 |
|---|---|
| boolean offer(E e) | 插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度O（logN），注意：空间不够时候会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检测优先级队列是否为空，空返回true |
例子：
import java.util.PriorityQueue; public class Test { public static void main(String[] args) { // 初始化一个整数数组 int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5}; PriorityQueue<Integer> q = new PriorityQueue<>(arr.length); // 将数组中的元素添加到优先级队列中 for (int e : arr) { q.offer(e); } // 打印优先级队列中有效元素的个数 System.out.println(q.size()); // 获取并打印优先级队列中优先级最高的元素（即最小值，因为是最小堆） System.out.println(q.peek()); // 从优先级队列中删除两个元素 q.poll(); q.poll(); // 打印删除两个元素后，优先级队列中有效元素的个数 System.out.println(q.size()); // 获取并打印当前优先级最高的元素 System.out.println(q.peek()); // 向优先级队列中插入一个新的元素 q.offer(0); // 获取并打印插入新元素后的优先级最高的元素 System.out.println(q.peek()); // 清空优先级队列中的所有有效元素 q.clear(); // 检测优先级队列是否为空，并打印结果 if (q.isEmpty()) { System.out.println("优先级队列已经为空!!!"); } else { System.out.println("优先级队列不为空"); } } } 
——这样我们就大致的了解了如何操作Java中的优先级队列了！！！
4.优先级队列的使用
优先级队列（Priority Queue）是一种特殊的数据结构，用于处理具有优先级的元素。它的主要特点是能够高效地插入元素并以优先级顺序访问和删除元素。以下是优先级队列的一些主要应用场景：
1. 任务调度
场景: 操作系统和调度系统常常需要管理多个任务，每个任务具有不同的优先级。
用法: 优先级队列可以用来实现任务调度系统，其中优先级高的任务会被优先执行。比如，操作系统的进程调度器会使用优先级队列来决定哪个进程应该优先获得 CPU 时间。
2. 事件驱动模拟
场景: 在模拟系统（如网络仿真或离散事件模拟）中，事件会在未来的某个时间点发生。
用法: 优先级队列用于存储和处理这些事件，确保在模拟中按事件的发生时间顺序处理它们。
3. 图算法
场景: 在计算图的最短路径（如 Dijkstra 算法）或最小生成树（如 Prim 算法）时，需要按边的权重或节点的距离进行操作。
用法: 使用优先级队列可以有效地管理和访问图中的边或节点，以支持这些算法的高效执行。
4. 数据流处理
场景: 数据流中的数据可能具有不同的重要性或优先级。
用法: 在处理实时数据流时，优先级队列可以用来根据数据的优先级顺序处理数据。
这样我们就大致的了解了Java中的优先级队列在日常中的使用地方了！
以上就是本篇文章的全部内容了~~~
