優(yōu)先隊列PriorityQueue，有空了解一下嗎？
前言
PriorityQueue這個隊列不知道大家使用過嗎，反正我用的很少，主要對它不是很了解，今天我?guī)ьI大家剖析下PriorityQueue這個優(yōu)先級隊列。
PriorityQueue介紹
顧名思義，PriorityQueue是優(yōu)先隊列的意思。優(yōu)先隊列的作用是能保證每次取出的元素都是隊列中權值最小的。這里牽涉到了大小關系，元素大小的評判可以通過元素本身的自然順序（natural ordering），也可以通過構造時傳入的比較器。
- PriorityQueue實現了Queue接口，最大的特點是存取具有優(yōu)先級，就是根據元素的順序來決定
- PriorityQueue是一個無界的容器
- PriorityQueue底層是基于堆實現的
- 不允許放入null元素
- PriorityQueue不是線程安全的
圖片
以上是PriorityQueue的類圖,
- 繼承了AbstractQueue抽象類，實現了Queue接口，具備隊列的操作方法
- 實現了Seriablizable接口，支持序列化
構造方法
方法 | 說明 |
PriorityQueue() | 構造一個初始容量為11的優(yōu)先隊列 |
PriorityQueue(Comparator<? super E> comparator) | 構造一個自定義排序器的優(yōu)先隊列 |
PriorityQueue(SortedSet<? extends E> c) | 構造一個基于SortedSet內容的優(yōu)先隊列 |
關鍵方法
方法 | 說明 |
add(E e) | 添加元素，如果超過隊列長度，拋出異常 |
offer(E e) | 添加元素，如果超過隊列長度返回false |
remove() | 獲取下個元素，如果沒有拋出異常 |
poll() | 獲取下個元素，如果沒有返回null |
element() | 查看下個元素的內容，如果沒有拋異常 |
peek() | 查看下個元素的內容，如果沒有返回null |
使用案例
- 優(yōu)先隊列功能測試
@Test
public void test1() {
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(5);
queue.offer(4);
queue.offer(1);
queue.offer(9);
queue.offer(3);
queue.offer(2);
// 打印，排序
Integer poll = null;
while ((poll = queue.poll()) != null) {
System.out.println(poll);
}
}運行結果：
圖片
- 自定義排序器
@Test
public void test2() {
// 自定義排序，倒序
Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
queue.offer(5);
queue.offer(4);
queue.offer(1);
queue.offer(9);
queue.offer(3);
queue.offer(2);
// 打印，排序
Integer poll = null;
while ((poll = queue.poll()) != null) {
System.out.println(poll);
}
}運行結果：
圖片
實現機制
PriorityQueue通過堆實現，具體說是通過完全二叉樹（complete binary tree）實現的小頂堆（任意一個非葉子節(jié)點的權值，都不大于其左右子節(jié)點的權值），也就意味著可以通過數組來作為PriorityQueue的底層實現。
圖片
上圖中我們給每個元素按照層序遍歷的方式進行了編號，如果你足夠細心，會發(fā)現父節(jié)點和子節(jié)點的編號是有聯系的，更確切的說父子節(jié)點的編號之間有如下關系：
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通過上述三個公式，可以輕易計算出某個節(jié)點的父節(jié)點以及子節(jié)點的下標。這也就是為什么可以直接用數組來存儲堆的原因。
源碼解析
成員變量
transient Object[] queue;
/**
* The number of elements in the priority queue.
*/
private int size = 0;
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
*/
private final Comparator<? super E> comparator;
/**
* The number of times this priority queue has been
* <i>structurally modified</i>. See AbstractList for gory details.
*/
transient int modCount = 0;- queue就是實際存儲元素的數組。
- size表示當前元素個數。
- comparator為比較器，可以為null。
- modCount記錄修改次數。
構造方法
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}- 初始化了queue和comparator
添加元素offer
public boolean offer(E e) {
// 如果元素為空，拋出空指針
if (e == null)
throw new NullPointerException();
// 修改次數+1
modCount++;
int i = size;
// 首先確保數組長度是夠的，如果不夠，調用grow方法動態(tài)擴展。
if (i >= queue.length)
grow(i + 1);
size = i + 1;
// 如果是第一次添加，直接添加到第一個位置即可 (queue[0]=e)
if (i == 0)
queue[0] = e;
else
// 否則將其放入最后一個位置，但同時向上調整，直至滿足堆的性質 (siftUp)
siftUp(i, e);
return true;
}private void grow(int 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);
}如果原長度比較小，大概就是擴展為兩倍，否則就是增加50%，使用Arrays.copyOf方法拷貝數組。
private void siftUp(int k, E x) {
// 如果比較器為空
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}參數k表示插入位置，x表示新元素。k初始等于數組大小，即在最后一個位置插入。代碼的主要部分是：往上尋找x真正應該插入的位置，這個位置用k表示。
怎么找呢？新元素(x)不斷與父節(jié)點(e)比較，如果新元素(x)大于等于父節(jié)點(e)，則已滿足堆的性質，退出循環(huán)，k就是新元素最終的位置，否則，將父節(jié)點往下移(queue[k]=e)，繼續(xù)向上尋找。
總結
優(yōu)先級可以有相同的，內部元素不是完全有序的，如果遍歷輸出，除了第一個，其他沒有特定順序。查看頭部元素的效率很高，為O(1)，入隊、出隊效率比較高，為O(log2(N))，構建堆的效率為O(N)。根據值查找和刪除元素的效率比較低，為O(N)。
