文章首發(fā)csdn博客地址：https://blog.csdn.net/u013277209?viewmode=contents
一：PriorityQueue實現(xiàn)方式
Java中PriorityQueue實現(xiàn)了Queue接口空执，不允許放入null元素；其通過堆實現(xiàn)澜驮，具體說是通過完全二叉樹（complete binary tree）實現(xiàn)的小頂堆（任意一個非葉子節(jié)點的權(quán)值较店，都不大于其左右子節(jié)點的權(quán)值）祈秕，也就意味著可以通過數(shù)組來作為PriorityQueue的底層實現(xiàn)唯蝶。
二：源碼分析
重要變量以及構(gòu)造函數(shù)
- 根據(jù)堆的特性，存儲結(jié)構(gòu)肯定是數(shù)組详瑞。
- 支持不同優(yōu)先級掂林，肯定有比較器，也就是說支持自定義排序和順序排序蛤虐。
- PriorityQueue的構(gòu)造函數(shù)有很多党饮，主要參數(shù)是容量和比較器。
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
//默認容量11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//堆的存儲結(jié)構(gòu)驳庭，存儲元素
transient Object[] queue;
//當前存儲的元素數(shù)量
private int size = 0;
//自定義比較器
private final Comparator<? super E> comparator;
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
擴容機制
每次擴容刑顺，當前容量小于64時就擴容為原來的2倍+2，當前容量大于等于64時擴容為原來的1.5倍饲常。
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add()和offer()
add(E e)和offer(E e)的語義相同蹲堂，都是向優(yōu)先隊列中插入元素，只是Queue接口規(guī)定二者對插入失敗時的處理不同贝淤，前者在插入失敗時拋出異常柒竞，后則則會返回false。對于PriorityQueue這兩個方法其實沒什么差別播聪。
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)//不允許放入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);//調(diào)整
return true;
}
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;//parentNo = (nodeNo-1)/2
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0) //調(diào)用比較器的比較方法,
break; //如果當前值大于等于父節(jié)點則跳出循環(huán)
queue[k] = e;//如果當前值小于父節(jié)點，則父節(jié)點與當前值交換位置
k = parent;//當前節(jié)點位置調(diào)整為原父節(jié)點位置离陶，進入下一次循環(huán)
}
queue[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;
}
新加入的元素x可能會破壞小頂堆的性質(zhì)稼虎，因此需要進行調(diào)整。調(diào)整的過程為：從k指定的位置開始招刨，將x逐層與當前點的parent進行比較并交換霎俩，直到滿足x >= queue[parent]為止。注意這里的比較可以是元素的自然順序沉眶，也可以是依靠比較器的順序打却。
element()和peek()
element()和peek()的語義完全相同，都是獲取但不刪除隊首元素谎倔，也就是隊列中權(quán)值最小的那個元素柳击，二者唯一的區(qū)別是當方法失敗時前者拋出異常，后者返回null片习。根據(jù)小頂堆的性質(zhì)捌肴，堆頂那個元素就是全局最小的那個彤守；由于堆用數(shù)組表示，根據(jù)下標關(guān)系哭靖，0下標處的那個元素既是堆頂元素具垫。所以直接返回數(shù)組0下標處的那個元素即可。
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
remove()和poll()
remove()和poll()方法的語義也完全相同试幽，都是獲取并刪除隊首元素筝蚕，區(qū)別是當方法失敗時前者拋出異常，后者返回null铺坞。由于刪除操作會改變隊列的結(jié)構(gòu)起宽，為維護小頂堆的性質(zhì)，需要進行必要的調(diào)整济榨。
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];//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 siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
//首先找到左右孩子中較小的那個坯沪，記錄到c里，并用child記錄其下標
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;//然后用c取代原來的值
k = child;
}
queue[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;
}
上述代碼首先記錄0下標處的元素擒滑，并用最后一個元素替換0下標位置的元素腐晾，之后調(diào)用siftDown()方法對堆進行調(diào)整，最后返回原來0下標處的那個元素（也就是最小的那個元素）丐一。重點是siftDown(int k, E x)方法藻糖，該方法的作用是從k指定的位置開始，將x逐層向下與當前點的左右孩子中較小的那個交換库车，直到x小于或等于左右孩子中的任何一個為止巨柒。
remove(Object o)
remove(Object o)方法用于刪除隊列中跟o相等的某一個元素（如果有多個相等，只刪除一個）柠衍，該方法不是Queue接口內(nèi)的方法洋满，而是Collection接口的方法。由于刪除操作會改變隊列結(jié)構(gòu)珍坊，所以要進行調(diào)整牺勾；又由于刪除元素的位置可能是任意的，所以調(diào)整過程比其它函數(shù)稍加繁瑣垫蛆。具體來說禽最，remove(Object o)可以分為2種情況：1. 刪除的是最后一個元素腺怯。直接刪除即可袱饭，不需要調(diào)整。2. 刪除的不是最后一個元素呛占，從刪除點開始以最后一個元素為參照調(diào)用一次siftDown()即可虑乖。此處不再贅述。
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
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;
}
