一、结构
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,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
jdk源码, jdk源码 jdk源码, jdk源码, jdk源码, jdk源码 jdk源码 jdk源码 jdk源码
java JDK 源码java JDK 源码java JDK 源码java JDK 源码java JDK 源码java JDK 源码java JDK 源码
对于想了解JDK源码的朋友来说,通过调试JDK源码来学习是一个常用的方法。但是默认的情况下eclipse是不支持进入jdk源码中进行调试和显示当前变量的。 我们要明白在jdk中,sun对rt.jar中的类编译时,去除了调试信息,这样...
jdk源码(完整版)。最新最全的jdk源码,网上基本上都是阉割版的
JDK源码阅读笔记
jdk源码 完整可用,开发程序必备啊。
JDK源码阅读笔记
jdk源码+hotspot
下载后直接去本机jdk目录里替换jdk中的src.zip 再打开idea就能看到中文版的源码注释 示例 https://blog.csdn.net/a7459/article/details/106495622
jdk源码包
对jdk中的动态代理执行过程进行了详细跟踪,并反编译了动态代理调用自动生成的代理类,并对其进行了详细讲解。
jdk源码jdk1.8.0_181,src源码文件
第一步:安装完jdk之后,打开jdk所在目录,里面有个src.zip,这就是此jdk的所有源码 第二步:找到之后我们开始导入,选中项目点击右键,选中Build Path栏中的Configure Build Path,在Libraries中我们打开JRE ...
jdk 8u60 源码下载: 导入请阅读IMPORT_README Main: sun.misc.Launcher
jdk1.6 源码
jdk6 源码jdk6 源码jdk6 源码jdk6 源码jdk6 源码jdk6 源码
JDK源码选读
关于调试jdk源码显示源码变量值的rt.jar重编译包
压缩包中为JDK8的源码,在源码的注释下方附带的中文翻译,是本压缩包的亮点,下方为局部代码,示范给大家: * Sole constructor. Programmers cannot invoke this constructor. * It is for use by code emitted ...