PriorityQueue
定义:
是个基于优先级堆的极大优先级队列。
此队列按照在构造时所指定的顺序对元素排序,既可以根据元素的自然顺序来指定排序(参阅 Comparable),也可以根据 Comparator 来指定,这取决于使用哪种构造方法。
优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)。
此队列的头是按指定排序方式的最小元素。如果多个元素都是最小值,则头是其中一个元素——选择方法是任意的。
队列的检索操作:
队列检索操作 poll、remove、peek 和 element 访问处于队列头的元素。
poll(): 获取并移除此队列的头,如果此队列为空,则返回 null。
peek():获取但不移除此队列的头;如果此队列为空,则返回 null。
remove(Object c):从此队列中移除指定元素的单个实例(如果存在)。
element:获取但不移除此队列的头。此方法与 peek
唯一的不同在于:此队列为空时将抛出一个异常。
除非队列为空,否则此实现返回 peek 的结果。
优先级队列是无界的,但是有一个内部容量,控制着用于存储队列元素的数组的大小。它总是至少与队列的大小相同。随着不断向优先级队列添加元素,其容量会自动增加。无需指定容量增加策略的细节。
注意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 comparator)
使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器comparator来排序其元素。
注意7:此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。
PriorityQueue的内部实现浅析 :
PriorityQueue对元素采用的是堆排序,头是按指定排序方式的最小元素。堆排序只能保证根是最大(最小),整个堆并不是有序的。方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的。实例1的结果也正好与此相符。
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue();
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//按照字母的asc||码排序
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函数实现,最终跟踪到函数:
/**
* 添加元素后,重新调整堆的过程,这里从下向上调整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 void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
/**
* 比较器为空的一趟筛选过程。
* PS:元素必须自己已经实现了Comparable方法
* 否则将抛出异常
*/
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
再比如remove()函数,去除指定元素后剩下的元素该如何变化?跟踪源码得到:
private E removeAt(int i) {
assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);//剩下的元素重新建堆
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
这个函数的实现方法是,将队尾元素取出,插入到位置i,替代被删除的元素,然后做相应的调整,保证二叉树的有序,即任意节点都是以它为根节点的子树中的最小节点。进一步的代码就留给有兴趣的读者自行分析,要说明的是,对于 queue这样的二叉树结构有一个特性,即如果数组的长度为length,那么所有下标大于length/2的节点都是叶子节点,其它的节点都有子节点。
最后附一对PriorityQueue实现的详细解析地址:http://zhouyunan2010.iteye.com/blog/1244846
总结:可以看到这种算法的实现,充分利用了树结构在搜索操作时的优势,效率又高于维护一个全部有序的队列
相关推荐
JAVA:PriorityQueue
优先级队列头文件priorityqueue.h
PriorityQueue-MEX-Matlab 优先级队列 matlab
算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-...
PriorityQueue 优先队列实现C# PriorityQueueLib: 基于二进制堆的最小/最大优先级队列实现PriorityQueueTests: PriorityQueue单元测试
PriorityQueue是Java中的一个优先级队列,它可以根据元素的优先级对元素进行排序,并且允许高效地获取和删除最高优先级的元素。
Java优先队列(PriorityQueue)示例Java开发Java经验技巧共5页.pdf.zip
优先级队列cpp文件PriorityQueue.cpp
主要为大家详细介绍了JDK源码之PriorityQueue,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Lists_Stack_Queue_PriorityQueue.java
优先队列使用 O(LogN) 复杂度为测试类实现 PriorityQueue。
主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
PriorityQueue PriorityQueue是最小/最大PriorityQueue的Javascript实现。 近期变动 V1.0 在1.0版中,删除了对setComparator(func)和setEquals(func)的支持。 这些方法导致了意外的行为。 需要这些功能时,请...
优先级队列是一种队列结构,是0个或多个元素的集合,每个元素都有一个优先权,PriorityQueue被内置于JDK中,本文就来解析Java中PriorityQueue优先级队列结构的源码及用法.
NULL 博文链接:https://robblog.iteye.com/blog/566114
主要介绍了java优先队列PriorityQueue中Comparator的用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
keap:Keap是一种堆数据结构,具有稳定的PriorityQueue和稳定的Keapsort排序算法
*push() 将一个元素置于priority queue中 top() 返回priority queue中的“下一个元素” pop() 从priority queue 中移除一个元素 注意:如果priority queue 内没有元素,执行top()和pop()会导致未定义的行为,应该先...
优先队列.NET Core的一个简单而又高效的优先级队列,它使用最小堆作为基础数据...new PriorityQueue ();queue . Enqueue ( " A " , 2 );queue . Enqueue ( " B " , 1 );queue . Enqueue ( " C " , 3 );while ( queue