一、结构
PriorityQueue是一个堆,任意节点都是以它为根节点的子树中的最小节点
堆的逻辑结构是完全二叉树状的,存储结构是用数组去存储的,随机访问性好。最小堆的根元素是最小的,最大堆的根元素是最大的
这是一个最小堆的逻辑结构
这是他的存储结构,是用数组来存储的。
可以看到,i下标的数组元素,他的父节点是(i-1)/2,他的左右节点分别是i*2+1,i*2+2
二、容量
2.1初始容量11
2.2扩展容量
private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); }
当容量不足的时候,会调用此方法,如果当前容量较小(小于64),则将容量增大一倍+2,如果当前容量较大,则容量增大一半
三、插入
插入元素会调用siftUp方法。
private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; }
当优先队列不指定比较器的时候,插入元素,会调用siftUpComparable
k表示元素将要插入的位置
这个方法的意思是,在以k为子节点的子树插入元素x,并保持该子树的顺序。(把k看作这个子树的叶子节点)
step1:得出父元素的下标
strp2:计算出要插入元素的位置k。如果插入元素大于父元素,将父元素移动到k的位置,k移动到其父元素,并从第一步开始循环执行
step3:在k的位置插入元素
四、删除
private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = queue[child]; int right = child + 1; if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key; }
删除会调用这个方法。删除都是将队尾的元素替换掉删除掉的位置
k表示元素将要插入的位置
这个方法的意思是,在k的子树插入元素x,并保持k位置子树的顺序(x是其子树的最小节点)。(把k看作这个子树的根节点)
这里要注意,像这种二叉树结构,下标大于size<<2都是叶子节点,其他的节点都有子节点。所以注意到循环条件,如果k是叶子节点的下标,则直接替换,因为其已经没有子树了,那么肯定是以其为根节点的最小元素
step1:算出k的左右节点的下标
step2:如果k大于左右节点中的最小一个,则k与最小的节点互换位置,并循环step1
step3:在k位置赋值x
查看原文:http://blog.zswlib.com/2016/10/31/jdk%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90priorityqueue/
相关推荐
JDK源码之PriorityQueue解析 一、优先队列的应用 优先队列是程序开发中常用的数据结构之一。它可以应用于多个领域,如操作系统的进程调度、爬虫系统的任务调度等。在这些应用中,优先队列可以确保高优先级的任务或...
**Java Development Kit (JDK) 源码详解** JDK,即Java Development Kit,是Java编程语言的核心组件,包含了编译器、运行时环境、工具集和其他必要的资源,用于开发和运行Java应用程序。这里提到的"jdk源码(完整版...
对于想了解JDK源码的朋友来说,通过调试JDK源码来学习是一个常用的方法。但是默认的情况下eclipse是不支持进入jdk源码中进行调试和显示当前变量的。 我们要明白在jdk中,sun对rt.jar中的类编译时,去除了调试信息,这样...
JDK源码阅读笔记
JDK源码阅读笔记
Java JDK源码是Java开发工具包的原始代码集合,它为开发者提供了深入理解Java平台工作原理的机会。JDK源码包含了许多核心类库,如`javax`、`com`、`org`、`java`以及`launcher`和`sunw`等包下的类和接口。这些源文件...
最后,`.jcheck`可能是源码静态分析工具的输出或配置,这类工具用于检查源码质量,发现潜在的错误和不符合编码规范的地方。了解这些工具的使用,可以帮助我们在开发过程中保持代码的整洁和一致性。 总的来说,深入...
8. **异常处理**:JDK中的`java.lang.Throwable`类是所有异常的基类,源码分析能让我们了解异常的层次结构和捕获、处理机制。 9. **并发工具**:`java.util.concurrent`包提供了高级并发工具,如`ExecutorService`...
下载后直接去本机jdk目录里替换jdk中的src.zip 再打开idea就能看到中文版的源码注释 示例 https://blog.csdn.net/a7459/article/details/106495622
通过阅读和分析JDK1.8的源码,开发者不仅可以深入了解Java语言的实现,还能学习到优秀的编程实践和设计模式,为日常开发工作提供强大支持。同时,对于优化代码性能、解决并发问题以及深入理解Java生态系统有着不可...
10. **性能优化**:书中可能会介绍如何通过分析JDK源码来找出性能瓶颈,并提供优化建议,例如通过JVM调优参数调整内存配置,或者使用并发工具进行性能提升。 以上只是部分可能涵盖的内容,实际书籍可能还涉及更多的...
第一步:安装完jdk之后,打开jdk所在目录,里面有个src.zip,这就是此jdk的所有源码 第二步:找到之后我们开始导入,选中项目点击右键,选中Build Path栏中的Configure Build Path,在Libraries中我们打开JRE ...
《深入解析JDK1.7源码:补全sun包下的源码》 在Java开发过程中,理解JDK源码是提升技术深度的关键步骤。JDK1.7版本的源码提供了对Java语言核心库的深入洞察,而sun包下的源码更是其中的重要组成部分,因为它们包含...
jdk6 源码jdk6 源码jdk6 源码jdk6 源码jdk6 源码jdk6 源码
【描述】"jdk源码包"意味着这个压缩文件包含了Java开发工具集(JDK)的所有源代码。通过分析这些源码,开发者可以学习到Java语言的内部工作原理,包括类库、虚拟机(JVM)以及各种工具的实现细节。 【标签】"jdk"和...
关于调试jdk源码显示源码变量值的rt.jar重编译包
安卓系统源码、JDK源码、OkHttp源码分析项目。通过阅读代码并注释的方式进行源码的学习。_analysis-for-source-code-of-Android
JDK源码,JDK源码,JDK源码,JDK源码,JDK源码,JDK源码,JDK源码
《深入理解可调试和注释的JDK源码》 在Java开发中,对JDK源码的理解至关重要,它能够帮助我们深入理解语言底层的工作原理,优化代码性能,解决复杂问题。本文将围绕"可以debug和加注释的jdk源码"这一主题,探讨如何...
源码分析可以揭示它们的内部结构和操作算法,这对于理解性能和选择合适的集合类型很有帮助。 8. **网络编程**:`java.net`包包含了网络通信的基础组件,如Socket和ServerSocket。通过源码,开发者可以深入理解网络...