JDK中的java.util.PriorityQueue实现方法不同于上面这些方法,它是基于堆的。
堆本质是一棵二叉树,其中所有的元素都可以按全序语义(参见附录说明)进行比较。用 堆来进行存储需要符合以下规则:
1.数据集中的元素可以用全序语义进行比较;
2.每个节点的元素必须大于或小于该节点的孩子节点的元素;
3.堆是一棵完全二叉树。
用堆来实现优先队列,跟节点始终是优先权最大的元素节点。
插入的思路是这样的,当插入一个元素时。先将这个元素插入到队列尾,然后将这个新插入的元素和它的父节点进行优先权的比较,如果比父节点的优先权要大,则和父节点呼唤位置,然后再和新的父节比较,直到比新的父节点优先权小为止,参见图2和图3
这个寻找新插入元素位置的过程对应于java.util.PriorityQueue源代码中的
Java代码
Java代码
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
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;
}
Java代码
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
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;
}
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
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;
}
不是二叉树结构吗?不是节点吗,为什么这里看到的是操作数组?我原来有这样的 疑问,因为之前自己实现过的二叉树只是止于链式结构。然而,树存在如下特点:
1.根节点的数据总是在数组的位置[0]
2.假设一个非跟节点的数据在数组中的位置[i],那么它的父节点总是在位置[(i-1)/2]
3.假设一个节点的数据在数组中的位置为[i],那么它的孩子(如果有)总是在下面的这两个位置:
左孩子在[2*i+1]
右孩子在[2*i+2]
基于这些特点,用数组来表示数会更加方便。源代码中int parent = (k - 1) >>> 1等价于int parent = (k - 1) / 2;对于这里涉及到的位运算,可以参见附录文档。
从优先队列中删除优先权最大的元素的思路是将队列尾的元素值赋给跟节点,队列为赋 值为null。然后检查新的根节点的元素优先权是否比左右子节点的元素的优先权大,如果 比左右子节点的元素的优先权小,就交换位置,重复这个过程,直到秩序正常。参见图4
相关推荐
主要为大家详细介绍了JDK源码之PriorityQueue,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
JDK11安装包,JDK11安装包JDK11安装包,JDK11安装包JDK11安装包,JDK11安装包JDK11安装包,JDK11安装包JDK11安装包,JDK11安装包JDK11安装包,JDK11安装包JDK11安装包,JDK11安装包JDK11安装包,JDK11安装包JDK11...
jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助文档jdk8帮助...
mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk1.8安装包!mac系统jdk...
jdk7 jdk8 jdk9 jdk10 jdk11 jdk12 jdk13 jdk14 (win-64位) 资源共享
jdk源代码下载 喜欢研究的下 jdk源代码下载 喜欢研究的下 jdk源代码下载 喜欢研究的下
Jdk的Timer 实现定时器,本例代码包括Handler 发送消息的简单实现过程 定时器 Timer,在这里演示一个进度条不断更新
协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤...
配置JDK环境,处理windows下存在多种JDK版本情况下,如何进行完美的在多个JDK版本的切换
用jdk原生api实现一些简单的加密算法,详情见:http://blog.csdn.net/zhong1113/article/details/50451751
分别使用jdk和cglib实现动态代理,包含UML图。还有相关的博客链接:http://blog.csdn.net/y_love_f/article/details/46345581.博客中有具体的代理解释
通过JDK动态代理机制实现增强,来理解AOP底层的实现
日志框架. 实现了动态的切换和log4j类似功能. 采用jdk1.4 log为底层实现. 下载后可以自己定制相关功能. 可以进一步完善.有兴趣可以加QQ:934547801一起讨论
JDK大全 JDK1.6 JDK1.7 JDK1.8 JDK1.9 JDK10 JDK11 JDK12
jdk1.8+springMVC实现http接口rsa加密解密
jdk内存设置 jdk内存设置 jdk内存设置 jdk内存设置 jdk内存设置 jdk内存设置
优先级队列是一种队列结构,是0个或多个元素的集合,每个元素都有一个优先权,PriorityQueue被内置于JDK中,本文就来解析Java中PriorityQueue优先级队列结构的源码及用法.
Jdk15泛型的实现
jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk配置jdk...
JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK11、JDK...