最近在項(xiàng)目開發(fā)中開發(fā)了全雙工異步長連接的通訊組件，內(nèi)部用到了延遲隊列。而延遲隊列的內(nèi)部實(shí)現(xiàn)的存儲是用到了優(yōu)先隊列，當(dāng)時看C++的數(shù)據(jù)結(jié)構(gòu)時，了解過優(yōu)先隊列，用的存儲是二叉樹的邏輯，應(yīng)該叫完全二叉樹，也可以叫做最大堆。
下面看一下二叉樹的算法，主要看插入和刪除。
二叉樹顧名思義就像一棵樹，每個節(jié)點(diǎn)下最多可以掛兩個節(jié)點(diǎn)，如圖
在優(yōu)先隊列中存儲的方式就是 queue = {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q};
若當(dāng)前節(jié)點(diǎn)下標(biāo)為i 那么它的子節(jié)點(diǎn) 左側(cè) = 2*i+1 右側(cè) = 2*i +2。優(yōu)先隊列顧名思義，就是優(yōu)先權(quán)最大的排在隊列的頭部，而優(yōu)先權(quán)的判斷是根據(jù)對象的compare方法比較獲取的，保證根節(jié)點(diǎn)的優(yōu)先級一定比子節(jié)點(diǎn)的優(yōu)先級大。所以放入到優(yōu)先隊列的元素要么實(shí)現(xiàn)了Comparable接口，要么在創(chuàng)造這個優(yōu)先隊列時，指定一個比較器。
下面我們來看一下優(yōu)先隊列的構(gòu)造函數(shù)
- private static final int DEFAULT_INITIAL_CAPACITY = 11;
- private final Comparator<? super E> comparator;
- public PriorityQueue() {
- this(DEFAULT_INITIAL_CAPACITY, null);
- }
- 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;
- }
在空構(gòu)造器初始化時，數(shù)組隊列的大小為11，比較器為null。這樣的話，放入優(yōu)先隊列的對象要實(shí)現(xiàn)comparable接口，也可以判斷隊列中不能存放null元素。
現(xiàn)在我們來看一下往隊列中添加一個對象的過程。
- public boolean add(E e) {
- return offer(e);
- }
- public boolean offer(E e) {
- if (e == null)
- throw new NullPointerException();
- modCount++;
- int i = size;
- if (i >= queue.length)
- grow(i + 1);
- size = i + 1;
- if (i == 0)
- queue[0] = e;
- else
- siftUp(i, e);
- return true;
- }
可以看到，優(yōu)先隊列中不可能存在null元素,添加元素首先把隊列修改次數(shù)++，判斷是否超過內(nèi)部數(shù)組的長度，超過后增加數(shù)組的長度 grow(i+1)
- private void grow(int minCapacity) {
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- int oldCapacity = queue.length;
- // Double size if small; else grow by 50%
- int newCapacity = ((oldCapacity < 64)?
- ((oldCapacity + 1) * 2):
- ((oldCapacity / 2) * 3));
- if (newCapacity < 0) // overflow
- newCapacity = Integer.MAX_VALUE;
- if (newCapacity < minCapacity)
- newCapacity = minCapacity;
- queue = Arrays.copyOf(queue, newCapacity);
- }
如果數(shù)組長度小于64 是按照一倍長度增長的，長度超過64，每次增長原來的百分之50，如果長度超過了int的最大值，那就設(shè)置為
Integer.MAX_VALUE，如果新的長度小于需要增長的長度，就是設(shè)置成這個長度，最后復(fù)制原來的對象到新的數(shù)組。
這樣數(shù)組長度擴(kuò)展了，設(shè)置size+1。如果是空的優(yōu)先隊列，就把新元素添加到隊列頭部。如果不是空，那就根據(jù)compareTo來判斷新加入的元素的優(yōu)先級別，那么我們來看一下siftUp方法
- private void siftUp(int k, E x) {
- if (comparator != null)
- siftUpUsingComparator(k, x);
- else
- siftUpComparable(k, 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;
- }
-
- 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;
- }
如果在創(chuàng)建隊列的時候，指定了比較工具，那么就用比較器，比較器內(nèi)部實(shí)現(xiàn)，可以根據(jù)自己的定義的比較原則，也可以調(diào)用加入隊列的元素的compareTo方法（如果實(shí)現(xiàn)的話),比較方法變化自行定義。
我們主要看一下沒有比較器的排序方法siftUpComparable，如下圖
假設(shè)數(shù)字越小，優(yōu)先級別越高，K的位置是新插入元素將要放置的位置，加入插入的是 25，那么此元素的優(yōu)先級別小于它的父節(jié)點(diǎn)的優(yōu)先級，直接把25放在K的位置。假如放置的是8，優(yōu)先級別最高，所以 (k-1)>>>1 獲取父節(jié)點(diǎn)，與父節(jié)點(diǎn)比較，發(fā)現(xiàn)優(yōu)先級大于父節(jié)點(diǎn)，把父節(jié)點(diǎn)的值放入K, 把K的位置設(shè)置成父節(jié)點(diǎn)的下標(biāo)值，遞歸查詢父節(jié)點(diǎn)，定位出K的位置，把新元素放入此位置。此種二叉樹算法大大降低了算法復(fù)雜度。
接下來我們看一下取走隊列頭部元素
- 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;
- }
- private void siftDown(int k, E x) {
- if (comparator != null)
- siftDownUsingComparator(k, x);
- else
- siftDownComparable(k, x);
- }
-
- private void siftDownComparable(int k, E x) {
- Comparable<? super E> key = (Comparable<? super E>)x;
- int half = size >>> 1; // loop while a non-leaf
- while (k < half) {
- int child = (k << 1) + 1; // assume left child is least
- Object c = queue[child];
- int right = child + 1;
- if (right < size &&
- ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
- c = queue[child = right];
- if (key.compareTo((E) c) <= 0)
- break;
- queue[k] = c;
- k = child;
- }
- queue[k] = key;
- }
-
- 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;
- }
如果隊列之有一個元素，就彈出這個元素，設(shè)置--size的位置為null。如果不是一個元素，彈出第一個元素，獲取數(shù)組最后的一個元素，開始調(diào)用siftDown(0, x);我們先來看一下圖解
這樣到poll掉隊列頭部元素后，隊列長度減一，所以最后的那個元素32的位置需要設(shè)置成null，這樣一來，需要填補(bǔ)隊列的頭，由于子節(jié)點(diǎn)一定小于等于父節(jié)點(diǎn)的優(yōu)先級，獲取父節(jié)點(diǎn)的子節(jié)點(diǎn)
int child = (k << 1) + 1; // 獲取左子節(jié)點(diǎn)的下標(biāo)
Object c = queue[child]; // 獲取左子節(jié)點(diǎn)
int right = child + 1; // 獲取右子節(jié)點(diǎn)的下標(biāo)
但右子節(jié)點(diǎn)不一定存在所以下面做了一個右節(jié)點(diǎn)不會為null的判斷，不為null的情況下，獲取兩個節(jié)點(diǎn)中優(yōu)先級高的一個
if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0){
c = queue[child = right];
}
//而下面這段代碼的意思是可能出現(xiàn)如下圖的情況
if (key.compareTo((E) c) <= 0){
break;
}
當(dāng)21移到隊列頭部時，隊列尾部的 32元素的優(yōu)先級 大于68和67的優(yōu)先級，可以直接把32元素放入到21的位置，直接結(jié)束循環(huán)，減少了下面空出元素的位置的重新排序算法。
用while（k<half) 因?yàn)閗如果>=half 的話，此下標(biāo)以下的節(jié)點(diǎn)無子節(jié)點(diǎn)，完全二叉樹定義，也可以推到。
優(yōu)先隊列 也就這兩個比較重要的方法，對于remove(Object o)方法，無非是刪除中間節(jié)點(diǎn)后的一種先向下排序，再向上排序的過程，可以自行查看。
歡迎交流。
