PriorityQueue 源码分析
概论PriorityQueue 类在 Java1.5 中引入并作为 Java Collections Framework 的一部分。PriorityQueue 是基于优先堆的一个无界队列,这个优先队列中的元素可以默认自然排序或者通过提供的 Comparator(比较器)在队列实例化的时排序。 优先队列不允许空值,而且不支持 non-comparable(不可比较)的对象,比如用户自定义的类。优先队列要求使用 Java Comparable 和 Comparator 接口给对象排序,并且在排序时会按照优先级处理其中的元素。如果你插入一个non-comparable对象,则会抛出一个 ClassCastException 异常。 优先队列的头是基于自然排序或者 Comparator 排序的最小元素。如果有多个对象拥有同样的排序,那么就可能随机地取其中任意一个。当我们获取队列时,返回队列的头对象。 优先队列的大小是不受限制的,但在创建时可以指定初始大小。它内部的有一个 “capacity” 管理着数组的大小,该数组用于存储队列的元素。它总是至少同队列大小一样大。当我们向优先队列增加元素的时候,队列大小会自动增加。并没有指定增长策略的细节。 该类和它的迭代器实现了 Collection 和 Iterator 接口所有可选的方法。迭代器提供的 iterator() 方法不保证遍历优先级队列的元素根据任何特别的顺序。如果你需要有序的遍历,考虑使用 Arrays.sort(pq.toArray()). PriorityQueue 是非线程安全的,所以 Java 提供了 PriorityBlockingQueue(实现 BlockingQueue 接口)用于 Java 多线程环境。 实现注意:该实现提供了 O(log(n)) 时间复杂度对于入队和出队方法:offer、poll、remove() 和 add;线性的时间 O(n) 对于 remove(object) 和 contains(object) 方法;和常量的时间O(1)对于检索方法:peek、element 和 size。 数据结构二叉堆是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆有两种:最大堆和最小堆。最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。 Priority queue 是一个 平衡二叉堆(平衡二叉树);树中所有的子节点必须大于等于父节点,而无需维护大小关系,是一个最小堆。 - 父节点与子节点的索引关系:
节点间的大小关系:
- 叶子节点和非叶子节点:
PriorityQueue 的源码分析基本属性先来看下 PriorityQueue 的定义 public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable { ?可以看到 PriorityQueue 继承了 AbstractQueue 抽象类,并实现了 Serializable 接口,AbstractQueue 抽象类实现了 Queue 接口,对其中方法进行了一些通用的封装,具体就不多看了。 下面看看里面定义的一些属性: // 默认初始化大小 我们看到 jdk 中的 PriorityQueue 的也是基于数组来实现一个二叉堆,并且注释中解释了我们前面的说法。PriorityQueue 是一个优先级队列,他可以由用户指定优先级,就是靠这个比较器的。?
虽然是无限队列,但是还是定义了一个最大容量:
* The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 最大容量 -8 是因为一些虚拟机会有些头字母保存在数组中,此外创造大容量的数组容易导致 OOM(数组容量超过虚拟机的限制)。 构造方法/** * 不带参数的构造函数,最终会给一个默认值public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY,null); } * 用户可以自己定义初始大小 可以发现其构造方法还是很多的,考虑到了各种不同的情况,同时也给了一些默认值。使用者可以根据使用场景,来进行初始化。 入队原理二叉堆(最小堆为例)的特点:
为了维护这个特点,二叉堆在添加元素的时候,需要一个"上移"的动作,什么是"上移"呢,我们继续用图来说明。 ?
?
结合上面的图解,我们来说明一下二叉堆的添加元素过程:
看完了这 4 张图,是不是觉得二叉堆的添加还是挺容易的,那么下面我们具体看下 PriorityQueue 的代码是怎么实现入队操作的吧。 * 插入一个元素,返回 true 代表添加成功boolean add(E e) { return offer(e); } * 插入一个元素到队列中去 offer(E e) { NullPointerException(); 接下来看看怎么扩容的,或者说扩容策略是怎么样的。
* Increases the capacity of the array. * * minCapacity the desired minimum capacity void grow( 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 的时候,基本上就是扩容一倍;但是当队列长度大于 64 之后,就会扩容 50%。扩容完成后,还要对新的容量进行判断是否符合要求,否则还是需要进一步调整的。然后再把队列的元素赋值到新的数组中。 int hugeCapacity(if (minCapacity < 0) overflow OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 需要理解的是,这里为什么当 minCapacity 小于 0 的时候,就代表超出 int 范围呢,我们来看下。 int 在java中占 4 个字节,一个字节 8 位,从 0 开始记,那么 4 个字节的最高位就是31,而 java 中的基本数据类型都是有符号的,所以最高位代表的是符号位。 int 的最大值 Integer.MAX_VALUE = 0111 1111?1111 1111 1111 1111 1111 1111,Integer.MAX_VALUE+1 = 1000 0000?0000 0000?0000 0000?0000 0000,此时最高位是符号位为 1,所以这个数是负数。负数的补码是在其原码的基础上,符号位不变,其余各位取反,最后 +1(即在反码的基础上 +1)。容量超了之后就会抛出 OOM。 接下去就是要看看元素是如何移动的。
?到这里,上移过程就结束了,可以发现整个上移过程还是比较简单的,起主要逻辑就是获取父节点,然后进行比较,要不要交换位置。插入操作的时间复杂度为 O(log(n)); 出队原理?对于二叉堆的出队操作,出队永远是要删除根元素,也就是最小的元素,要删除根元素,就要找一个替代者移动到根位置,相对于被删除的元素来说就是"下移"。
?
结合上面的图解,我们来说明一下二叉堆的出队过程:
看完了这 6 张图,下面我们具体看下 PriorityQueue 的代码是怎么实现出队操作的吧。 /** * 移除一个元素,如果存在的话 remove(Object o) { indexOf(o); if (i == -1false { removeAt(i); ; } } * 迭代的时候进行移除 removeEq(Object o) { for (int i = 0; i < size; i++if (o == queue[i]) { removeAt(i); ; } } ; } * 移除第 i 个位置的元素 ) E removeAt( i) { assert i >= 0 && i < size; 增加修改次数 modCount++int s = --size; if (s == i) removed last element ,如果是最后一位直接置null,表示删除 queue[i] = { E moved = (E) queue[s]; // 获取最后一位元素 queue[s] = ; siftDown(i,moved); // 第 i 位元素下移,同时最后一位元素要上移 为了保持二叉堆的各项数据大小不变性,需要在删除元素后,对原来的元素进行调整,下面看下是怎么下移的:
jdk 中,不是直接将根元素删除,然后再将下面的元素做上移,重新补充根元素;而是找出队尾的元素,并在队尾的位置上删除,然后通过根元素的下移,给队尾元素找到一个合适的位置,最终覆盖掉跟元素,从而达到删除根元素的目的。这样做在一些情况下,会比直接删除在上移根元素,或者直接下移根元素再调整队尾元素的位置少操作一些步奏(比如上面图解中的例子,不信你可以试一下^_^)。 该删除操作的最坏耗时为:n + 2log(n); 所以该操作的的时间复杂度为 O(n);
indexOf(object) 操作时间复杂度为 O(n);
removeAt(index) 操作时间复杂度为 O(log(n))
明白了二叉堆的入队和出队操作后,其他的方法就都比较简单了,下面我们再来看一个二叉堆中比较重要的过程,二叉堆的构造。 堆的构造堆的构造是通过一个 heapify 方法,下面我们来看下 heapify 方法的实现。
* Establishes the heap invariant (described above) in the entire tree,* assuming nothing about the order of the elements prior to the call. void heapify() { int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i,(E) queue[i]); } 这个方法很简单,就这几行代码,但是理解起来却不是那么容器的,我们来分析下。 假设有一个无序的数组,要求我们将这个数组建成一个二叉堆,你会怎么做呢?最简单的办法当然是将数组的数据一个个取出来,调用入队方法。但是这样做,每次入队都有可能会伴随着元素的移动,这么做是十分低效的。那么有没有更加高效的方法呢,我们来看下。 为了方便,我们将上面我们图解中的数组去掉几个元素,只留下7、6、5、12、10、3、1、11、15、4(顺序已经随机打乱)。ok、那么接下来,我们就按照当前的顺序建立一个二叉堆,暂时不用管它是否符合标准。 int a = [7,6,5,12,10,3,1,11,15,4 ];
我们观察下用 数组a 建成的二叉堆,很明显,对于叶子节点 4、15、11、1、3 来说,它们已经是一个合法的堆。所以只要最后一个节点的父节点,也就是最后一个非叶子节点 a[4]=10 开始调整,然后依次调整 a[3]=12,a[2]=5,a[1]=6,a[0]=7,分别对这几个节点做一次"下移"操作就可以完成了堆的构造。ok,我们还是用图解来分析下这个过程。 我们参照图解分别来解释下这几个步奏:
至此,调整完毕,建堆完成。 再来回顾一下,PriorityQueue的建堆代码,看看是否可以看得懂了。
?
1 private void heapify() { 2 for (int i = (size >>> 1) - 1; i >= 0; i--) 3 siftDown(i,(E) queue[i]); 4 } int?i = (size?>>> 1) - 1,这行代码是为了找寻最后一个非叶子节点,然后倒序进行"下移" siftDown 操作,是不是很显然了。? 其他清除优先级队列中所有节点?* Removes all of the elements from this priority queue. * The queue will be empty after this call returns. clear() { modCount++) queue[i] = ; size = 0; } 清除优先级队列中的所有节点。该操作的事件复杂度为:O(n); 迭代器优先级队列的迭代器并不保证遍历按照指定的顺序获取节点元素。这是因为当在迭代器中执行 remove 操作时,可能会涉及到一个未访问的元素被移动到了一个已经访问过的节点位置(删除操作时,当队尾节点被放置到待移除节点位置的情况下,需要调用 siftUp 方法,siftUp(index,object) 方法会升高待插入元素在树中的位置 index,直到待插入的元素大于或等于它待插入位置的父节点)。在迭代器操作中需要特殊处理。此时这些不幸的元素会在所有节点遍历完后才得以遍历。 @SuppressWarnings("unchecked") E next() { if (expectedModCount != modCount) ConcurrentModificationException(); 到这里 PriorityQueue 的基本操作就分析完了,明白了其底层二叉堆的概念及其入队、出队、建堆等操作,其他的一些方法代码就很简单了,这里就不一一分析了。? ? 参考文章:PriorityQueue 源码分析 PriorityQueue 源码分析 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |