- 浏览: 7936733 次
- 性别:
- 来自: 广州
文章分类
- 全部博客 (2425)
- 软件工程 (75)
- JAVA相关 (662)
- ajax/web相关 (351)
- 数据库相关/oracle (218)
- PHP (147)
- UNIX/LINUX/FREEBSD/solaris (118)
- 音乐探讨 (1)
- 闲话 (11)
- 网络安全等 (21)
- .NET (153)
- ROR和GOG (10)
- [网站分类]4.其他技术区 (181)
- 算法等 (7)
- [随笔分类]SOA (8)
- 收藏区 (71)
- 金融证券 (4)
- [网站分类]5.企业信息化 (3)
- c&c++学习 (1)
- 读书区 (11)
- 其它 (10)
- 收藏夹 (1)
- 设计模式 (1)
- FLEX (14)
- Android (98)
- 软件工程心理学系列 (4)
- HTML5 (6)
- C/C++ (0)
- 数据结构 (0)
- 书评 (3)
- python (17)
- NOSQL (10)
- MYSQL (85)
- java之各类测试 (18)
- nodejs (1)
- JAVA (1)
- neo4j (3)
- VUE (4)
- docker相关 (1)
最新评论
-
xiaobadi:
jacky~~~~~~~~~
推荐两个不错的mybatis GUI生成工具 -
masuweng:
(转)JAVA获得机器码的实现 -
albert0707:
有些扩展名为null
java 7中可以判断文件的contenttype了 -
albert0707:
非常感谢!!!!!!!!!
java 7中可以判断文件的contenttype了 -
zhangle:
https://zhuban.me竹板共享 - 高效便捷的文档 ...
一个不错的网络白板工具
在队列中,一般都是先进先出的,但其实java中提供了可以用户自定义权重的优先级队列.
本文小结一下:
PriorityQueue
PriorityQueue是个基于优先级堆的极大优先级队列。
此队列按照在构造时所指定的顺序对元素排序,既可以根据元素的自然顺序来指定排序(参阅 Comparable),
也可以根据 Comparator 来指定,这取决于使用哪种构造方法。优先级队列不允许 null 元素。
依靠自然排序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)。
此队列的头是按指定排序方式的最小元素。如果多个元素都是最小值,则头是其中一个元素——选择方法是任意的。
队列检索操作 poll、remove、peek 和 element 访问处于队列头的元素。
优先级队列是无界的,但是有一个内部容量,控制着用于存储队列元素的数组的大小。
它总是至少与队列的大小相同。随着不断向优先级队列添加元素,其容量会自动增加。无需指定容量增加策略的细节。
注意1:该队列是用数组实现,但是数组大小可以动态增加,容量无限。
注意2:此实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表, 则这些线程不应同时访问 PriorityQueue 实例,这时请使用线程安全的PriorityBlockingQueue 类。
注意3:不允许使用 null 元素。
注意4:此实现为插入方法(offer、poll、remove() 和 add 方法)提供 O(log(n)) 时间;
为 remove(Object) 和 contains(Object) 方法提供线性时间;
为检索方法(peek、element 和 size)提供固定时间。
注意5:方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。
至于原因可参考下面关于PriorityQueue的内部实现
如果需要按顺序遍历,请考虑使用 Arrays.sort(pq.toArray())。
注意6:可以在构造函数中指定如何排序。如:
PriorityQueue()
使用默认的初始容量(11)创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity)
使用指定的初始容量创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器comparator来排序其元素。
注意7:此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。
PriorityQueue的内部实现
PriorityQueue对元素采用的是堆排序,头是按指定排序方式的最小元素。堆排序只能保证根是最大(最小),整个堆并不是有序的。
方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的。
例子:
public static void main(String[] args) {
PriorityQueue<String> pq = new PriorityQueue<String>();
pq.add("dog");
pq.add("apple");
pq.add("fox");
pq.add("easy");
pq.add("boy");
while (!pq.isEmpty()) {
System.out.print("left:");
for (String s : pq) {
System.out.print(s + " ");
}
System.out.println();
System.out.println("poll(): " + pq.poll());
}
}
输出的结果如下:
left:apple boy fox easy dog
poll(): apple
left:boy dog fox easy
poll(): boy
left:dog easy fox
poll(): dog
left:easy fox
poll(): easy
left:fox
poll(): fox
可以看到,虽然PriorityQueue保持了队列顶部元素总是最小,但内部的其它元素的顺序却随着元素的减少始终处于变化之中。
察看源代码来一探究竟。从Netbeans中非常方便的连接到PriorityQueue的add函数实现,
最终跟踪到函数private void siftUpComparable(int k, E 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;
}
相对于add的操作,该函数的入口参数k是指新加入元素的下标,而x 就是新加入的元素。
乍一看,这个函数的实现比较令人费解,尤其是parent的定义。通过进一步分析了解到,
PriorityQueue内部成员数组 queue其实是实现了一个二叉树的数据结构,这棵二叉树的根节点是queue[0],
左子节点是queue[1],右子节点是queue[2],而 queue[3]又是queue[1]的左子节点,依此类推,给定元素queue,
该节点的父节点是queue[(i-1)/2]。因此 parent变量就是对应于下标为k的节点的父节点。
弄清楚了这个用数组表示的二叉树,就可以理解上面的代码中while 循环进行的工作是,
当欲加入的元素小于其父节点时,就将两个节点的位置交换。这个算法保证了如果只执行add操作,那么queue这个二叉树是有序的:
该二叉树中的任意一个节点都小于以该节点为根节点的子数中的任意其它节点。这也就保证了queue[0],即队顶元素总是所有元素中最小的。
需要注意的是,这种算法无法保证不同子树上的两个节点之间的大小关系。举例来说,queue[3]一定会小于queue[7],但是未必会小于queue[9],因为queue[9]不在以queue[3]为根节点的子树上。
弄清楚了add的操作,那么当队列中的元素有变化的时候,对应的数组queue又该如何变化呢?察看函数poll(),
最终追中到函数private E removeAt(int i),代码如下:
private E removeAt(int i) {
assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue == moved) {
siftUp(i, moved);
if (queue != moved)
return moved;
}
}
return null;
}
这个函数的实现方法是,将队尾元素取出,插入到位置i,替代被删除的元素,然后做相应的调整,保证二叉树的有序,
即任意节点都是以它为根节点的子树中的最小节点。进一步的代码就留给有兴趣的读者自行分析,
要说明的是,对于 queue这样的二叉树结构有一个特性,即如果数组的长度为length,
那么所有下标大于length/2的节点都是叶子节点,其它的节点都有子节点。
总结:可以看到这种算法的实现,充分利用了树结构在搜索操作时的优势,效率又高于维护一个全部有序的队列
------------------------------------------------------------------------
总结:其实上面說了这么多,就是在說,在add,poll的时候都是在使用堆排序!建立的是小堆!
再看例子:
输出的是:
Initial priority queue values are: [3, 4, 5, 6, 7, 8, 9]
Head of the queue is: 3
Priority queue values after poll: [4, 6, 5, 9, 7, 8]
为什么是4, 6, 5, 9, 7, 8呢?其实就是在3出队后,对剩下的4,5,6,7,8,9进行
重新建立小堆!
----------------------------------------------------------------------------
再来看自定义的comparator比较器
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue<Integer> qi = new PriorityQueue<Integer>();
qi.add(5);
qi.add(2);
qi.add(1);
qi.add(10);
qi.add(3);
while (!qi.isEmpty()){
System.out.print(qi.poll() + ",");
}
System.out.println();
System.out.println("-----------------------------");
Comparator<Integer> cmp;
cmp = new Comparator<Integer>() {
public int compare(Integer e1, Integer e2) {
return e2 - e1;
}
};
Queue<Integer> q2 = new PriorityQueue<Integer>(5,cmp);
q2.add(2);
q2.add(8);
q2.add(9);
q2.add(1);
while (!q2.isEmpty()){
System.out.print(q2.poll() + ",");
}
}
输出的是:9 8 2 1
---------------------------------------------------------------------------
还可以用这个轻松解决TOP K问题,两个不错的资料参考:
1 http://my.oschina.net/leejun2005/blog/135085
2 http://marvin-space.info/blog/algo_priority-queue/
本文小结一下:
PriorityQueue
PriorityQueue是个基于优先级堆的极大优先级队列。
此队列按照在构造时所指定的顺序对元素排序,既可以根据元素的自然顺序来指定排序(参阅 Comparable),
也可以根据 Comparator 来指定,这取决于使用哪种构造方法。优先级队列不允许 null 元素。
依靠自然排序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)。
此队列的头是按指定排序方式的最小元素。如果多个元素都是最小值,则头是其中一个元素——选择方法是任意的。
队列检索操作 poll、remove、peek 和 element 访问处于队列头的元素。
优先级队列是无界的,但是有一个内部容量,控制着用于存储队列元素的数组的大小。
它总是至少与队列的大小相同。随着不断向优先级队列添加元素,其容量会自动增加。无需指定容量增加策略的细节。
注意1:该队列是用数组实现,但是数组大小可以动态增加,容量无限。
注意2:此实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表, 则这些线程不应同时访问 PriorityQueue 实例,这时请使用线程安全的PriorityBlockingQueue 类。
注意3:不允许使用 null 元素。
注意4:此实现为插入方法(offer、poll、remove() 和 add 方法)提供 O(log(n)) 时间;
为 remove(Object) 和 contains(Object) 方法提供线性时间;
为检索方法(peek、element 和 size)提供固定时间。
注意5:方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。
至于原因可参考下面关于PriorityQueue的内部实现
如果需要按顺序遍历,请考虑使用 Arrays.sort(pq.toArray())。
注意6:可以在构造函数中指定如何排序。如:
PriorityQueue()
使用默认的初始容量(11)创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity)
使用指定的初始容量创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器comparator来排序其元素。
注意7:此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。
PriorityQueue的内部实现
PriorityQueue对元素采用的是堆排序,头是按指定排序方式的最小元素。堆排序只能保证根是最大(最小),整个堆并不是有序的。
方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的。
例子:
public static void main(String[] args) {
PriorityQueue<String> pq = new PriorityQueue<String>();
pq.add("dog");
pq.add("apple");
pq.add("fox");
pq.add("easy");
pq.add("boy");
while (!pq.isEmpty()) {
System.out.print("left:");
for (String s : pq) {
System.out.print(s + " ");
}
System.out.println();
System.out.println("poll(): " + pq.poll());
}
}
输出的结果如下:
left:apple boy fox easy dog
poll(): apple
left:boy dog fox easy
poll(): boy
left:dog easy fox
poll(): dog
left:easy fox
poll(): easy
left:fox
poll(): fox
可以看到,虽然PriorityQueue保持了队列顶部元素总是最小,但内部的其它元素的顺序却随着元素的减少始终处于变化之中。
察看源代码来一探究竟。从Netbeans中非常方便的连接到PriorityQueue的add函数实现,
最终跟踪到函数private void siftUpComparable(int k, E 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;
}
相对于add的操作,该函数的入口参数k是指新加入元素的下标,而x 就是新加入的元素。
乍一看,这个函数的实现比较令人费解,尤其是parent的定义。通过进一步分析了解到,
PriorityQueue内部成员数组 queue其实是实现了一个二叉树的数据结构,这棵二叉树的根节点是queue[0],
左子节点是queue[1],右子节点是queue[2],而 queue[3]又是queue[1]的左子节点,依此类推,给定元素queue,
该节点的父节点是queue[(i-1)/2]。因此 parent变量就是对应于下标为k的节点的父节点。
弄清楚了这个用数组表示的二叉树,就可以理解上面的代码中while 循环进行的工作是,
当欲加入的元素小于其父节点时,就将两个节点的位置交换。这个算法保证了如果只执行add操作,那么queue这个二叉树是有序的:
该二叉树中的任意一个节点都小于以该节点为根节点的子数中的任意其它节点。这也就保证了queue[0],即队顶元素总是所有元素中最小的。
需要注意的是,这种算法无法保证不同子树上的两个节点之间的大小关系。举例来说,queue[3]一定会小于queue[7],但是未必会小于queue[9],因为queue[9]不在以queue[3]为根节点的子树上。
弄清楚了add的操作,那么当队列中的元素有变化的时候,对应的数组queue又该如何变化呢?察看函数poll(),
最终追中到函数private E removeAt(int i),代码如下:
private E removeAt(int i) {
assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue == moved) {
siftUp(i, moved);
if (queue != moved)
return moved;
}
}
return null;
}
这个函数的实现方法是,将队尾元素取出,插入到位置i,替代被删除的元素,然后做相应的调整,保证二叉树的有序,
即任意节点都是以它为根节点的子树中的最小节点。进一步的代码就留给有兴趣的读者自行分析,
要说明的是,对于 queue这样的二叉树结构有一个特性,即如果数组的长度为length,
那么所有下标大于length/2的节点都是叶子节点,其它的节点都有子节点。
总结:可以看到这种算法的实现,充分利用了树结构在搜索操作时的优势,效率又高于维护一个全部有序的队列
------------------------------------------------------------------------
总结:其实上面說了这么多,就是在說,在add,poll的时候都是在使用堆排序!建立的是小堆!
再看例子:
public class PriorityQueueDemo { public static void main(String args[]) { // create priority queue PriorityQueue < Integer > prq = new PriorityQueue < Integer > (); // insert values in the queue for ( int i = 3; i < 10; i++ ){ prq.add (new Integer (i)) ; } System.out.println ( "Initial priority queue values are: "+ prq); // get the head from the queue Integer head = prq.poll(); System.out.println ( "Head of the queue is: "+ head); System.out.println ( "Priority queue values after poll: "+ prq); } }
输出的是:
Initial priority queue values are: [3, 4, 5, 6, 7, 8, 9]
Head of the queue is: 3
Priority queue values after poll: [4, 6, 5, 9, 7, 8]
为什么是4, 6, 5, 9, 7, 8呢?其实就是在3出队后,对剩下的4,5,6,7,8,9进行
重新建立小堆!
----------------------------------------------------------------------------
再来看自定义的comparator比较器
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue<Integer> qi = new PriorityQueue<Integer>();
qi.add(5);
qi.add(2);
qi.add(1);
qi.add(10);
qi.add(3);
while (!qi.isEmpty()){
System.out.print(qi.poll() + ",");
}
System.out.println();
System.out.println("-----------------------------");
Comparator<Integer> cmp;
cmp = new Comparator<Integer>() {
public int compare(Integer e1, Integer e2) {
return e2 - e1;
}
};
Queue<Integer> q2 = new PriorityQueue<Integer>(5,cmp);
q2.add(2);
q2.add(8);
q2.add(9);
q2.add(1);
while (!q2.isEmpty()){
System.out.print(q2.poll() + ",");
}
}
输出的是:9 8 2 1
---------------------------------------------------------------------------
还可以用这个轻松解决TOP K问题,两个不错的资料参考:
1 http://my.oschina.net/leejun2005/blog/135085
2 http://marvin-space.info/blog/algo_priority-queue/
发表评论
-
复习:强迫线程顺序执行方式
2019-01-03 23:42 1569方法1: 三个线程,t1,t2,t3,如果一定要按顺序执行, ... -
(转)不错的前后端处理异常的方法
2019-01-02 23:16 2018前言 在 Web 开发中, 我们经常会需要处理各种异常, 这是 ... -
info q的极客时间大咖说等资料下载
2018-08-15 08:40 3464info q的极客时间大咖说等资料下载,还有不少思维导图 链 ... -
CXF 客户端超时时间设置(非Spring配置方式)
2018-07-03 22:38 2232import org.apache.cxf.endpoint. ... -
(转)synchronized关键字画像:正确打开方式
2018-06-14 09:25 490https://mp.weixin.qq.com/s/b3Sx ... -
CountDownLatch的例子
2018-06-13 14:10 684public class StatsDemo { ... -
两道面试题,带你解析Java类加载机制
2018-06-12 16:29 607https://mp.weixin.qq.com/s/YTa0 ... -
Spring中获取request的几种方法,及其线程安全性分析
2018-06-11 09:03 669https://mp.weixin.qq.com/s/KeFJ ... -
内部类小结
2018-06-06 10:25 433https://mp.weixin.qq.com/s/hErv ... -
JVM虚拟机小结1
2018-06-04 20:43 5391 jps -l //列出详细的类名和进程ID 2)jps ... -
windows下自带命令行工具查看CPU资源情况等
2018-06-04 12:53 3096微软提供了不少命令行 ... -
(收藏)深入分析Java的序列化与反序列化
2018-05-30 15:21 614https://mp.weixin.qq.com/s/T2Bn ... -
apache common包中的序列化工具
2018-05-30 09:10 1843什么是序列化 我们的 ... -
JAVA8 JVM的变化: 元空间(Metaspace)
2018-05-24 22:30 963本文将会分享至今为至我收集的关于永久代(Permanent G ... -
(转)服务器性能指标(一)——负载(Load)分析及问题排查
2018-05-21 21:03 1360原创: Hollis Hollis 负载 ... -
(转)对象复用
2018-05-20 15:27 857public class Student { priv ... -
mapreduce中入门中要注意的几点
2018-05-06 08:59 669在 mapreduce中,比如有如下的词: I love b ... -
HDFS的基本操作
2018-05-02 21:47 937-mkdir 在HDFS创建目录 ... -
一个不错的开源工具类,专门用来解析日志头部的,好用
2018-05-02 20:00 768一个不错的开源工具类,专门用来解析日志头部的,好用。 http ... -
介绍个不错的RESTFUL MOCK的工具wiremock
2018-04-27 21:02 1904介绍个不错的RESTFUL MOCK的工具wiremock,地 ...
相关推荐
### Java中的PriorityQueue详解 #### 类概述 `PriorityQueue`是Java集合框架的一部分,它是一个基于优先级堆的无界优先级队列。这个队列的元素可以按照它们的自然顺序或者是通过构造队列时提供的`Comparator`进行...
优先级队列头文件priorityqueue.h
而"pradeepr-roboticist-PriorityQueue-MEX-Matlab-1f6c329"可能是项目仓库的一个特定版本,由作者pradeepr-roboticist维护,版本号为1f6c329,这通常是Git版本控制系统中的一个提交ID,代表了该项目在某一时刻的源...
Java的优先队列(PriorityQueue)是Java集合框架中一个重要的数据结构,它是一个基于堆实现的无界队列。优先队列中的元素按照优先级排序,最高的优先级元素总是在队列的头部。在Java中,PriorityQueue类位于`java....
PriorityQueue 优先队列实现C# PriorityQueueLib: 基于二进制堆的最小/最大优先级队列实现PriorityQueueTests: PriorityQueue单元测试
优先队列(PriorityQueue)是Java集合框架中的一个重要组件,它提供了一种高效处理具有优先级的数据结构。在Java中,PriorityQueue类实现了Queue接口,它遵循最小堆的原理,即队首元素总是队中最小的(默认情况下)...
JDK源码之PriorityQueue解析 一、优先队列的应用 优先队列是程序开发中常用的数据结构之一。它可以应用于多个领域,如操作系统的进程调度、爬虫系统的任务调度等。在这些应用中,优先队列可以确保高优先级的任务或...
Java 的优先队列 PriorityQueue 原理及实例分析 Java 的优先队列 PriorityQueue 是 Queue 接口的实现,可以对其中元素进行排序,可以放基本数据类型的包装类(如:Integer,Long 等)或自定义的类。PriorityQueue ...
Java中的PriorityQueue是一种特殊的队列,它遵循优先级原则,即队列中的元素根据其优先级进行排列。PriorityQueue在JDK中内置,基于二叉堆数据结构实现,特别是最小堆,这意味着队列头部的元素总是具有最低的优先级...
`siftUpUsingComparator()` 方法会比较新元素 `x` 和其父节点 `e`,如果 `x` 比 `e` 大(对于最大堆),或者 `x` 比 `e` 小(对于最小堆),那么会交换它们的位置,确保堆的有序性。这个过程一直持续到 `x` 找到其...
在Java编程中,优先队列(PriorityQueue)是一种特殊的队列,它按照元素的优先级进行出队。这种数据结构在实现多路归并排序(Multi-Merge Sort)时非常有用,因为它能有效地处理多个已排序的输入流,并将它们合并成...
PriorityQueue是Java中的一个优先级队列,它可以根据元素的优先级对元素进行排序,并且允许高效地获取和删除最高优先级的元素。
**PriorityQueue带优先级的队列** `PriorityQueue`是Java集合框架中的一种特殊队列,它基于优先堆实现,可以自动对队列中的元素进行排序。与普通队列不同,`PriorityQueue`不是先进先出(FIFO)的数据结构,而是...
优先级队列cpp文件PriorityQueue.cpp
PriorityQueue PriorityQueue是最小/最大PriorityQueue的Javascript实现。 近期变动 V1.0 在1.0版中,删除了对setComparator(func)和setEquals(func)的支持。 这些方法导致了意外的行为。 需要这些功能时,请...
在Java编程语言中,`Lists`, `Stack`, `Queue`, 和 `PriorityQueue` 是四个重要的数据结构,它们各自在不同的场景下发挥着关键作用。这些数据结构是Java集合框架的一部分,帮助开发者有效地组织和操作数据。 1. **...
默认情况下,`PriorityQueue` 使用的小顶堆结构,即队首元素总是最小的。然而,在某些场景下,我们可能需要构建一个大顶堆,使队首元素为最大值。本文将介绍如何通过重写`Comparator`接口的`compare`方法来实现这个...
`android-priorityqueue`是一个专门为Android设计的轻量级库,它提供了一个简单且干净的解决方案来处理待办事项(To-Do)列表,使得任务按照优先级进行排序和处理。这个库的核心理念是帮助开发者快速实现具有优先级...
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
优先队列(PriorityQueue)是数据结构中的一种特殊类型,它在处理元素的插入和删除时,不遵循传统的先进先出(FIFO)或后进先出(LIFO)原则,而是根据元素的优先级来决定操作顺序。在许多算法问题和实际应用中,...