PriorityQueue内部机制浅析

 

 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的结果也正好与此相符。

Java代码  

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()); }
 } 

 

输出的结果如下：

Java代码  

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函数实现，最终跟踪到函数：

Java代码  

/**  
 * 添加元素后，重新调整堆的过程，这里从下向上调整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():

Java代码  

//获取并移除根节点
public E poll() {
        if (size == 0)
            return null;
        int s = --size;//数组大小减一
        modCount++;
        E result = (E) queue[0];//获得根节点
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);//重新建堆，保证根节点为最小元素
        return result;
    }

 

Java代码  

 

/**  
 *  
 * 节点的调整：从此节点开始，由上至下进行位置调整。把小值上移。  
 * 可以称之为一次筛选，从一个无序序列构建堆的过程就是一个不断筛选的过程.  
 * 直到筛选到的节点为叶子节点，或其左右子树均大于此节点就停止筛选。  
 */  

private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

 

Java代码  

/**  
 * 比较器为空的一趟筛选过程。  
 * 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()函数，去除指定元素后剩下的元素该如何变化？跟踪源码得到：

Java代码  

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

总结：可以看到这种算法的实现，充分利用了树结构在搜索操作时的优势，效率又高于维护一个全部有序的队列