PriorityQueue优先队列实现原理

一、什么是优先队列

   优先队列不是按照普通对象先进先出原FIFO则进行数据操作，其中的元素有优先级属性，优先级高的元素先出队。本文提到的PriorityQueue队列，是基于最小堆原理实现。

   需要注意：PriorityQueue继承了AbstractQueue没有实现BlockingQueue接口，所以没有take阻塞方法。

二、什么是最小堆

    最小堆是一个完全二叉树，所谓的完全二叉树是一种没有空节点的二叉树。

    最小堆的完全二叉树有一个特性是根节点必定是最小节点，子女节点一定大于其父节点。还有一个特性是叶子节点数量=全部非叶子节点数量+1

    在 PriorityQueue队列中，基于数组保存了完全二叉树。所以在已知任意一个节点在数组中的位置，就可以通过一个公式推算出其左子树和右子树的下标。已知节点下标是i，那么他的左子树是2*i+1，右子树是2*i+2。

三、PriorityQueue队列的存取原理

     1、首先看下源码

[java] view plain copy

print?

1. /** 
2.  * Inserts item x at position k, maintaining heap invariant by 
3.  * promoting x up the tree until it is greater than or equal to 
4.  * its parent, or is the root. 
5.  * 
6.  * To simplify and speed up coercions and comparisons. the 
7.  * Comparable and Comparator versions are separated into different 
8.  * methods that are otherwise identical. (Similarly for siftDown.) 
9.  * 
10.  * @param k the position to fill 
11.  * @param x the item to insert 
12.  */  
13. private void siftUp(int k, E x) {  
14.     if (comparator != null)  
15.         siftUpUsingComparator(k, x);  
16.     else  
17.         siftUpComparable(k, x);  
18. }  

在调用offer(E e)方法入队时，首先进行非null判断，然后是grow方法扩容，紧接着就是siftUp方法调整节点位置，那么是如何调整的呢？为什么要调整？

2、为什么要调整节点顺序？

因为这是一个最小堆，最小堆必须要严格按照子节点大于父亲节点的顺序做数组中存放。

3、如何调整？

siftup方法有个if-else判断，如果有比较器，则使用siftUpUsingComparator(k, x);如果没有则调用siftUpComparable(k, x);这个方法会默认给一个比较器。

比较什么呢？？我们说最小堆实现了这个队列，队列一定有入队操作，入队是元素首先进入队列尾，然后和自己的父节点比较，像冒泡一样将该节点冒到合适的位置，即比自己的父亲节点大，比自己的儿子节点小。

[java] view plain copy

print?

1. private void siftUpComparable(int k, E x) {  
2.        Comparable<? super E> key = (Comparable<? super E>) x;  
3.        while (k > 0) {  
4.            int parent = (k - 1) >>> 1;  
5.            Object e = queue[parent];  
6.            if (key.compareTo((E) e) >= 0)  
7.                break;  
8.            queue[k] = e;  
9.            k = parent;  
10.        }  
11.        queue[k] = key;  
12.    }  

4、如何出队

[java] view plain copy

print?

1. public E poll() {  
2.         if (size == 0)  
3.             return null;  
4.         int s = --size;  
5.         modCount++;  
6.         E result = (E) queue[0];  
7.         E x = (E) queue[s];  
8.         queue[s] = null;  
9.         if (s != 0)  
10.             siftDown(0, x);  
11.         return result;  
12.     }  
13.   
14.  private void siftDownComparable(int k, E x) {  
15.         Comparable<? super E> key = (Comparable<? super E>)x;  
16.         int half = size >>> 1;        // loop while a non-leaf  
17.         while (k < half) {  
18.             int child = (k << 1) + 1; // assume left child is least  
19.             Object c = queue[child];  
20.             int right = child + 1;  
21.             if (right < size &&  
22.                 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)  
23.                 c = queue[child = right];  
24.             if (key.compareTo((E) c) <= 0)  
25.                 break;  
26.             queue[k] = c;  
27.             k = child;  
28.         }  
29.         queue[k] = key;  
30.     }  

出队和入队原理正好相反，每次出队也要进行siftDown操作，对元素顺序重新整理。

四、总结

PriorityQueue队列不适合进场出队入队的频繁操作，但是他的优先级特性非常适合一些对顺序有要求的数据处理场合。