住房城乡建设部门户网站,wordpress 不显示标题,中国网站有哪些,建e网官网效果图前言#xff1a;优先级队列#xff08;Priority Queue#xff09;是一种抽象数据类型#xff0c;其中每个元素都关联有一个优先级#xff0c;元素按照优先级顺序进行处理。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客 … 前言优先级队列Priority Queue是一种抽象数据类型其中每个元素都关联有一个优先级元素按照优先级顺序进行处理。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客 先让我们看一下本文大致的讲解内容 目录
1.优先队列的初识 1优先级队列的定义 2PriorityQueue的特性
2.优先级队列的模拟实现
3.优先级队列中常用API 1创建优先级队列 2插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空
4.优先级队列的使用
1. 任务调度
2. 事件驱动模拟
3. 图算法
4. 数据流处理 1.优先队列的初识 1优先级队列的定义 在开始学习Java中优先级队列的使用之前先让我们了解一下什么是Java中的优先级队列PriorityQueue 优先级队列Priority Queue是一种抽象数据类型其中每个元素都关联有一个优先级元素按照优先级顺序进行处理。与标准队列不同优先级队列中的元素处理顺序并非按插入顺序而是按照优先级高低来决定。 如果读者看了优先级队列的定义之后还是不是太理解什么是优先级队列那么现在我们使用一个日常生活中的例子来帮助你理解 ——例如在医院急诊室虽然你可能先到但是医生会根据病人的病情严重程度来决定治疗顺序。病情严重的病人例如心脏病发作的病人会被优先治疗而病情较轻的病人例如轻微的感冒会被安排在后面。 这样我相信读者就对优先级队列有了初步的认识了 2PriorityQueue的特性 Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队而对于PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的而本文我们主要介绍是PriorityQueue。
其在Java集合框架中的关系图为 关于PriorityQueue的使用要注意 1. 使用时必须导入PriorityQueue所在的包即
import java.util.PriorityQueue; 2. PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出ClassCastException异常 3. 不能插入null对象否则会抛出NullPointerException 4. 没有容量限制可以插入任意多个元素其内部可以自动扩容 5. 插入和删除元素的时间复杂度为OlogN 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()创建一个空的优先级队列默认容量是11PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列注意 initialCapacity不能小于1否则IllegalArgumentException异常PriorityQueue(Collection? extends E c) 用一个集合来创建优先级队列
例子
import java.util.PriorityQueue;public class PriorityQueueDemo {public static void main(String[] args) {// 默认初始容量的优先级队列PriorityQueueInteger pq new PriorityQueue();// 指定初始容量的优先级队列PriorityQueueInteger pqWithCapacity new PriorityQueue(20);// 使用比较器的优先级队列PriorityQueueInteger pqWithComparator new PriorityQueue(new CustomComparator());}
}——这样我们就会常见Java中的优先级队列了
在了解了如何创建一个优先级队列之后接下来让我们看一下如何去操作这个创建的优先级队列。 2插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空
函数名功能boolean offer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度OlogN注意空间不够时候会进行扩容E peek()获取优先级最高的元素如果优先级队列为空返回nullE poll()移除优先级最高的元素并返回如果优先级队列为空返回nullint 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};PriorityQueueInteger 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中的优先级队列在日常中的使用地方了 以上就是本篇文章的全部内容了~~~
