中国网站建设公司,wordpress目录调用,鑫迪建站系统,建材网站咦咦咦#xff0c;各位小可爱#xff0c;我是你们的好伙伴——bug菌#xff0c;今天又来给大家普及Java SE相关知识点了#xff0c;别躲起来啊#xff0c;听我讲干货还不快点赞#xff0c;赞多了我就有动力讲得更嗨啦#xff01;所以呀#xff0c;养成先点赞后阅读的好… 咦咦咦各位小可爱我是你们的好伙伴——bug菌今天又来给大家普及Java SE相关知识点了别躲起来啊听我讲干货还不快点赞赞多了我就有动力讲得更嗨啦所以呀养成先点赞后阅读的好习惯别被干货淹没了哦~ 本文收录于「滚雪球学Java」专栏专业攻坚指数级提升助你一臂之力带你早日登顶欢迎大家关注收藏持续更新中upupup
环境说明Windows 10 IntelliJ IDEA 2021.3.2 Jdk 1.8文章目录 前言摘要PriorityQueue概述PriorityQueue的定义与特性PriorityQueue的底层实现 源代码解析PriorityQueue的构造函数添加元素删除元素 应用场景案例任务调度网络代理 优缺点分析优点缺点 类代码方法介绍public 测试用例测试代码演示测试结果测试代码分析 小结 总结附录源码 ☀️建议/推荐你关于我 前言 PriorityQueue是Java中一个非常常用的数据结构它可以实现基于优先级的排序常用于任务调度、事件处理等场景。本文将深入探讨Java中PriorityQueue的底层实现与源码分析帮助读者更好地理解PriorityQueue的内部原理。
摘要 本文将从PriorityQueue的定义、特性入手逐步分析其底层实现、源码解析以及应用场景案例、优缺点分析等方面全面深入地理解PriorityQueue。
PriorityQueue
概述
PriorityQueue的定义与特性 在Java中PriorityQueue是一个优先级队列它是基于数组实现的但是其中的元素不是按照插入顺序排列而是按照元素的优先级进行排序。你可以将任意类型的对象插入PriorityQueue中并且PriorityQueue会按照元素的自然顺序或者你自己定义的优先级顺序进行排序。 PriorityQueue是一个无界队列即队列的容量可以无限扩充。它是线程不安全的不支持null元素。默认情况下PriorityQueue是自然排序也就是小根堆也可以通过Comparator接口来指定元素的排序方式。
PriorityQueue的底层实现 PriorityQueue是基于数组实现的它的底层数据结构是一个小根堆。小根堆是一种完全二叉树满足一个性质即每个节点的值都小于或等于它的左右子节点的值。 在PriorityQueue中数组的第一个元素是堆顶也就是优先级最高的元素。每次插入一个元素时PriorityQueue会先将元素添加到数组末尾然后通过上浮操作来维护小根堆的性质。每次删除堆顶元素时PriorityQueue会先将数组末尾元素移动到堆顶然后通过下沉操作来维护小根堆的性质。
源代码解析
PriorityQueue的构造函数 public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}public PriorityQueue(Comparator? super E comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator);}public PriorityQueue(int initialCapacity, Comparator? super E comparator) {this.comparator comparator;this.queue new Object[initialCapacity];}PriorityQueue有四个构造函数默认构造函数、指定初始化容量的构造函数、指定Comparator的构造函数和同时指定初始化容量与Comparator的构造函数。 当不指定初始化容量和Comparator时将会使用默认值。默认容量为11Comparator为null。 如下是部分源码截图
添加元素 public boolean add(E e) {return offer(e);}public boolean offer(E e) {if (e null)throw new NullPointerException();modCount;int i size;if (i queue.length)grow(i 1);size i 1;if (i 0)queue[0] e;elsesiftUp(i, e);return true;}private void siftUp(int k, E x) {if (comparator ! null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}添加元素时会先判断队列是否已满如果已满则通过grow()方法进行扩容。接着会将元素添加到数组末尾然后通过siftUp()方法来维护小根堆的性质。 如果指定了Comparator则通过siftUpUsingComparator()方法来维护小根堆的性质否则通过siftUpComparable()方法维护小根堆的性质。这里的siftUp()方法还是比较关键的它是用来上浮元素维护小根堆的性质的。 删除元素 public E poll() {if (size 0)return null;int s --size;modCount;E result (E) queue[0];E x (E) queue[s];queue[s] null;if (s ! 0)siftDown(0, x);return result;}private void siftDown(int k, E x) {if (comparator ! null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x);}删除元素时会先判断队列是否为空。如果不为空就将堆顶元素取出作为返回值然后将数组末尾的元素移动到堆顶通过siftDown()方法来维护小根堆的性质。 如果指定了Comparator则通过siftDownUsingComparator()方法来维护小根堆的性质否则通过siftDownComparable()方法维护小根堆的性质。
拓展 这段代码是Java中PriorityQueue类中的poll()方法的实现。poll()方法用于从队列中取出并删除队列头部的元素如果队列为空则返回null。 该方法首先检查队列是否为空如果为空则返回null。否则将队列中的元素个数减1更新modCount属性表示这次操作改变了队列结构将队列头部的元素用变量result存储。接着将队列中最后一个元素用变量x存储并将队列中最后一个元素置为null。若队列还有元素调用siftDown()方法将变量x与队列中元素重新排序确保队列满足小根堆的性质。最后返回变量result即队列中被删除的元素。 在siftDown()方法中首先判断comparator是否为null。如果不为null则调用siftDownUsingComparator()方法否则调用siftDownComparable()方法。这两个方法都是用来重建小根堆的不同的是siftDownUsingComparator()方法通过比较器来实现排序而siftDownComparable()方法则通过元素的自然顺序来实现排序。
应用场景案例
任务调度 假设我们需要实现一个任务调度器能够按照任务的优先级来执行任务。我们可以将任务按照优先级添加到PriorityQueue中然后按照队列中任务的顺序依次执行。
public class Task implements ComparableTask {private int priority;private Runnable runnable;public Task(int priority, Runnable runnable) {this.priority priority;this.runnable runnable;}public void run() {runnable.run();}Overridepublic int compareTo(Task o) {return Integer.compare(priority, o.priority);}}public class MyTaskScheduler {private PriorityQueueTask queue;public MyTaskScheduler() {queue new PriorityQueue();}public void schedule(Task task) {queue.offer(task);}public void run() {while (!queue.isEmpty()) {Task task queue.poll();task.run();}}}分析代码 这段代码定义了一个Task类和一个MyTaskScheduler类用于实现任务调度。Task类包含了一个优先级和一个Runnable对象用于存储待执行的任务和它的优先级。MyTaskScheduler类包含了一个优先队列用于存储所有的任务并且包括了两个方法schedule()方法用于将任务加入到队列中run()方法则用于执行队列中的所有任务。 Task类实现了Comparable接口重写了compareTo()方法通过比较任务的优先级来判断哪个任务先执行。MyTaskScheduler类使用了Java自带的PriorityQueue优先队列保证了任务的执行顺序是按照优先级从高到低的顺序执行。在run()方法中使用一个while循环不断从队列中取出优先级最高的任务直到队列为空。对于每个任务调用它的run()方法来执行任务逻辑。 这段代码可以用于实现多个任务的调度通过设置不同的优先级来控制不同任务的执行顺序。同时使用优先队列可以保证任务按照优先级的顺序执行提高了任务执行的效率。
网络代理 假设我们需要实现一个网络代理能够按照ip包的优先级来转发数据。我们可以将ip包按照优先级添加到PriorityQueue中然后按照队列中ip包的顺序依次转发数据。
public class IpPacket implements ComparableIpPacket {private int priority;private byte[] data;public IpPacket(int priority, byte[] data) {this.priority priority;this.data data;}public byte[] getData() {return data;}Overridepublic int compareTo(IpPacket o) {return Integer.compare(priority, o.priority);}}public class MyNetworkProxy {private PriorityQueueIpPacket queue;public MyNetworkProxy() {queue new PriorityQueue();}public void send(IpPacket packet) {queue.offer(packet);}public void receive() {while (!queue.isEmpty()) {IpPacket packet queue.poll();// 转发数据}}}拓展 上面是一个简单的网络代理程序其中包含两个类IpPacket和MyNetworkProxy。 IpPacket类表示一个IP数据包包含数据的优先级和实际的数据。实现了Comparable接口用于优先级的排序。 MyNetworkProxy类表示一个网络代理通过维护一个优先级队列来实现数据包的转发。send方法用于将数据包添加到队列中receive方法用于从队列中取出优先级最高的数据包并进行转发。 在MyNetworkProxy中当队列不为空时每次从队列头取出优先级最高的数据包进行转发直到队列为空。 这个程序中的优先级队列可以保证高优先级的数据包先被发送以保证网络的效率和响应时间。
优缺点分析
优点
PriorityQueue是一个非常高效的数据结构它的插入和删除元素的时间复杂度都是O(log n)。PriorityQueue可以实现基于优先级的排序适用于任务调度、事件处理等场景。PriorityQueue在扩容时可以节省空间只需将数组容量增加一半即可。PriorityQueue支持自然排序和指定Comparator来定义元素的排序方式。
缺点
PriorityQueue是线程不安全的不适合在多线程环境下使用。如果需要在多线程环境下使用可以使用PriorityBlockingQueue。PriorityQueue不支持随机访问元素只能访问堆顶元素。如果需要随机访问元素可以使用TreeSet。
类代码方法介绍
public
public class PriorityQueueE extends AbstractQueueE implements java.io.Serializable {/*** 序列化 ID*/private static final long serialVersionUID -7720805057305804111L;/*** 默认初始容量*/private static final int DEFAULT_INITIAL_CAPACITY 11;/*** 底层数组用于存储堆元素*/transient Object[] queue;/*** 数组中元素的数量*/private int size 0;/*** 比较器用于确定堆中元素的顺序*/private final Comparator? super E comparator;/*** 修改次数用于判断在迭代过程中堆是否发生了修改*/transient int modCount 0;/*** 构造一个初始容量为11的PriorityQueue元素顺序按照自然顺序排列*/public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}/*** 构造一个指定初始容量的PriorityQueue元素顺序按照自然顺序排列*/public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}/*** 构造一个初始容量为11的PriorityQueue元素顺序按照指定比较器排列*/public PriorityQueue(Comparator? super E comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator);}/*** 返回PriorityQueue的头部元素如果队列为空则返回null*/public E peek() {if (size 0) {return null;}return (E) queue[0];}/*** 返回PriorityQueue中元素的数量*/public int size() {return size;}/*** 对元素进行排序排序的规则由比较器决定*/private void heapify() {for (int i (size 1) - 1; i 0; i--) {siftDown(i, (E) queue[i]);}}/*** 返回一个包含PriorityQueue中所有元素的数组*/Overridepublic Object[] toArray() {return Arrays.copyOf(queue, size);}以上是Java中PriorityQueue类的部分源码。PriorityQueue是一个堆可以存储任意类型的元素但是需要这些元素是可比较的可以按照一定的顺序进行排序。PriorityQueue实现了Queue接口因此可以像队列一样进行添加和删除元素并且堆的性质保证了每次返回的元素都是最优的。 如下是部分源码截图 具体分析如下 PriorityQueue类是一个泛型类使用类名后面的表示。 类中定义了一个序列化ID一个底层数组用于存储堆元素一个记录数组中元素数量的变量一个记录堆发生修改次数的变量以及一个比较器。其中比较器用于判断堆中元素的顺序。 类中定义了多个构造方法可以创建一个初始容量为11的PriorityQueue也可以指定初始容量和比较器。 PriorityQueue类实现了Queue接口中的offer、peek和poll方法。其中offer方法用于将元素添加到PriorityQueue中peek方法用于返回PriorityQueue的头部元素如果队列为空则返回nullpoll方法用于删除PriorityQueue的头部元素并返回该元素如果队列为空则返回null。 类中还定义了一个size方法用于返回PriorityQueue中元素的数量。 PriorityQueue类实现了Iterable接口因此可以迭代PriorityQueue中的元素。在此基础上类中定义了一个Itr迭代器类用于遍历PriorityQueue中的元素。其中由于堆不保证元素的顺序因此元素的顺序是不确定的。 类中还实现了一个使用指定的Collection构造PriorityQueue的方法用于将一个Collection中的元素添加到PriorityQueue中。 heapify方法用于对元素进行排序排序的规则由比较器决定。 toArray方法用于返回一个包含PriorityQueue中所有元素的数组。其中使用Arrays类的copyOf方法对底层数组进行复制和截取以保证只返回PriorityQueue中的有效元素。
测试用例 下面是一个简单的示例main函数使用Java中的PriorityQueue实现一个整数优先级队列并添加一些元素并打印结果
测试代码演示
package com.demo.javase.day70;import java.util.PriorityQueue;/*** Author bug菌* Date 2023-11-06 16:08*/
public class PriorityQueueTest {public static void main(String[] args) {PriorityQueueInteger pq new PriorityQueue();pq.add(5);pq.add(1);pq.add(10);pq.add(3);pq.add(2);System.out.println(队列中的元素(从小到大));while (!pq.isEmpty()) {System.out.print(pq.poll() );}}
}测试结果 根据如上测试用例本地测试结果如下仅供参考你们也可以自行修改测试用例或者添加更多的测试数据或测试方法进行熟练学习以此加深理解。
输出结果
队列中的元素(从小到大)
1 2 3 5 10在这个示例中我们创建了一个PriorityQueue对象pq并添加了5个整数元素。然后我们使用poll()方法按照优先级顺序逐个弹出元素并打印结果。注意PriorityQueue默认使用自然顺序从小到大因此我们不需要指定比较器。
实际执行结果如下 测试代码分析 根据如上测试用例在此我给大家进行深入详细的解读一下测试代码以便于更多的同学能够理解并加深印象。 如上测试用例演示了Java中的PriorityQueue优先队列的用法。在主方法中先创建了一个PriorityQueue对象pq并向其中添加了五个整数元素511032。然后通过while循环从队列中取出元素并打印因为PriorityQueue默认是小根堆所以打印出来的元素是从小到大排列的。最终输出结果为队列中的元素(从小到大)1 2 3 5 10
小结 本文通过对Java中PriorityQueue的定义、特性、底层实现及源码解析进行详细分析深入探讨了PriorityQueue的内部原理。PriorityQueue是一种基于数组实现的堆它可以按照元素的优先级进行排序常用于任务调度、事件处理等场景。PriorityQueue底层是一个小根堆在元素添加和删除时会通过上浮和下沉操作来维护小根堆的性质。同时本文也介绍了PriorityQueue的应用场景案例以及优缺点分析帮助读者更好地理解PriorityQueue。 总之PriorityQueue作为Java集合框架中的一个重要组成部分对于Java开发者来说是必不可少的知识点。读者可以通过学习本文加深对PriorityQueue的理解从而更好地应用于实际开发中。
总结 本文从PriorityQueue的定义、特性和底层实现入手深入剖析了Java中PriorityQueue的源码和应用场景案例并对其进行了优缺点分析。PriorityQueue是一种非常高效的数据结构可以实现基于优先级的排序适用于任务调度、事件处理等场景。但是需要注意的是它是线程不安全的不支持随机访问元素。在使用PriorityQueue时需要根据实际情况选择适合的数据结构和算法来解决问题。 … 好啦这期的内容就基本接近尾声啦若你想学习更多可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》本专栏致力打造最硬核 Java 零基础系列学习内容打造全网精品硬核专栏带你直线超车欢迎大家订阅持续学习。
附录源码 如上涉及所有源码均已上传同步在「Gitee」提供给同学们一对一参考学习辅助你更迅速的掌握。
☀️建议/推荐你 无论你是计算机专业的学生还是对编程有兴趣的小伙伴都建议直接毫无顾忌的学习此专栏「滚雪球学Java」bug菌郑重承诺凡是学习此专栏的同学均能获取到所需的知识和技能全网最快速入门Java编程就像滚雪球一样越滚越大指数级提升。 最后如果这篇文章对你有所帮助帮忙给作者来个一键三连关注、点赞、收藏您的支持就是我坚持写作最大的动力。 同时欢迎大家关注公众号:「猿圈奇妙屋」 以便学习更多同类型的技术文章免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。 关于我 我是bug菌CSDN | 掘金 | infoQ | 51CTO 等社区博客专家历届博客之星Top30掘金年度人气作者Top4051CTO年度博主Top12华为云 | 阿里云| 腾讯云等社区优质创作者全网粉丝合计15w 硬核微信公众号「猿圈奇妙屋」欢迎你的加入免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。
