什麼是 Queue
資料結構中的隊列，先進先出式的資料結構，所有新元素都插入隊列的末尾，移除元素都移除隊列的頭部。主要注意的時，Java中的Queue是一個接口。
Queue 源碼分析
public interface Queue<E> extends Collection<E> {
boolean add(E e); //往隊列插入元素，如果出現異常會抛出異常
boolean offer(E e); //往隊列插入元素，如果出現異常則傳回false
E remove(); //移除隊列元素，如果出現異常會抛出異常
E poll(); //移除隊列元素，如果出現異常則傳回null
E element(); //擷取隊列頭部元素，如果出現異常會抛出異常
E peek(); //擷取隊列頭部元素，如果出現異常則傳回null
}
上面六個函數總體上分為兩類：安全的會進行容量檢查的（add,remove,element）,如果隊列沒有值，則取元素會抛出IlleaglStatementException異常。不安全的不進行容量控制的(offer,poll,peek )。
AbstractQueue 是Queue 的抽象實作類， AbstractQueue 也繼承自 AbstractCollection 。AbstractQueue 實作的方法不多，主要就 add、remove、element 三個方法的操作失敗抛出了異常。
什麼是 PriorityQueue
PriorityQueue 優先級隊列， ，不同于普通的遵循FIFO(先進先出)規則的隊列,每次都選出優先級最高的元素出隊，優先隊列裡實際是維護了這樣的一個堆，通過堆使得每次取出的元素總是最小的（使用者可以自定義比較方法，相當于使用者設定優先級）。 PriorityQueue 是一個小頂堆，是非線程安全的；PriorityQueue不是有序的，隻有堆頂存儲着最小的元素；從資料的存儲結構看, PriorityQueue 一個數組;從邏輯結構看， PriorityQueue 是一棵平衡二叉樹。
什麼是 PriorityQueue
PriorityQueue 優先級隊列， ，不同于普通的遵循FIFO(先進先出)規則的隊列,每次都選出優先級最高的元素出隊，優先隊列裡實際是維護了這樣的一個堆，通過堆使得每次取出的元素總是最小的（使用者可以自定義比較方法，相當于使用者設定優先級）。 PriorityQueue 是一個小頂堆，是非線程安全的；PriorityQueue不是有序的，隻有堆頂存儲着最小的元素；從資料的存儲結構看, PriorityQueue 一個數組;從邏輯結構看， PriorityQueue 是一棵平衡二叉樹。
PriorityQueue 源碼分析
繼承關系
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable{
// 略
}
PriorityQueue 繼承了AbstractQueue 類，而AbstractQueue 類實作了Queue接口。
主要屬性
// 預設容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 存儲元素的數組，Object類型的
transient Object[] queue;
// 元素個數
int size;
// 比較器
private final Comparator<? super E> comparator;
// 修改次數
transient int modCount;
transient Object[] queue
源碼注釋
Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.
優先級隊列是一個平衡的二叉樹堆，queue[n]的兩個子節點queue[2n+1] and queue[2(n+1)]。 優先級隊列 按照 comparator 進行排序或者 按自然順序排序。 如果 comparator 為null ，堆中每一個節點 n 以及 n的後代d, n<=d。假設隊列為非空，則具有最小值的元素位于queue [0]中。
常用構造函數
- 1、建立一個優先隊列對象，預設大小，隊列中的元素按照自然順序排序。
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
- 2、建立一個指定大小的優先隊列對象，隊列中的元素按照自然順序排序。
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
- 3、建立一個預設大小(11)的優先隊列對象，隊列中的元素按照指定比較器進行排序。
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
- 4、根據指定的大小和比較器來建立一個優先隊列對象。
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;
}
add(e)/offer(e)方法介紹
add方法
插入一個元素到優先隊列中
add方法的源代碼如下：
public boolean add(E e) {
return offer(e);
}
從源碼中可以看出add方法直接調用了offer方法。
offer(e)方法
public boolean offer(E e) {
if (e == null) //檢查是否為null, 如果為null 則抛空指針異常
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) // 檢查容量是否足夠， 不足進行擴容
grow(i + 1); // 擴容函數
siftUp(i, e); // 在數組的末尾插入新的元素,向上調整，使之保持為二叉堆的特性。
size = i + 1;
return true;
}
1）首先檢查要添加的元素e是否為null，如果為null，則抛空指針異常，如果不為null，則進行2
2）判斷數組是否已滿，如果已滿，則進行擴容，否則将元素加入到數組末尾即可。
由于這個數組表示的是一個“二叉堆”，是以還需要進行相應的調整操作，使得這個數組在添加元素之後依然保持的是二叉堆的特性。
grow(int minCapacity)方法
//增加數組的容量
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
//如果比較小，則擴容為原來的2倍，否則隻擴容為原來的1.5倍
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);
}
hugeCapacity(int minCapacity) 方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
注：
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public static final int MAX_VALUE = 0x7fffffff;
當 大于 MAX_ARRAY_SIZE 時擴容記性了特殊處理
siftUp(int k, E x)方法
将元素x插入到queue[k]位置上，并進行調整使之具有二叉堆特性
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x); // 使用比較器 comparator
else
siftUpComparable(k, x);
}
siftUpUsingComparator和siftUpComparable源碼如下
從 位置 k 向數組起始位置 調整使之具有二叉堆特性，自下而上的堆化，
也就是 二叉堆插入元素思想操作：
可參見 拜托，面試别再問我堆（排序）了！
siftUpComparable(int k, E x)方法
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1; // 找 parent 父節點
Object e = queue[parent];
if (key.compareTo((E) e) >= 0) // 比較 按 自然順序 排列
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
siftUpUsingComparator(int k, E x)方法
@SuppressWarnings("unchecked")
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) // 使用比較器 comparator
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
poll()方法介紹
取出優先隊列中的第一個元素
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;
}
poll方法：取出queue[0]元素，然後将queue[size-1]插入到queue[0],然後自上而下堆化來保持二叉堆的特性。
siftDown(int k, E x)方法
//将元素x存儲在queue[k],并進行相應的調整
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
siftDownComparable(int k, E 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;
}
siftDownUsingComparator(int k, E x)方法
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(Object o) 方法介紹
移除指定元素
public boolean remove(Object o) {
int i = indexOf(o); // 判斷位置
if (i == -1) //沒有在數組中找到
return false;
else {
removeAt(i); //進行删除并調整
return true;
}
}
indexOf(Object o)方法
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++) // 數組周遊過程
if (o.equals(queue[i]))
return i;
}
return -1;
}
找到對象o在數組中出現的第一個索引
emoveAt(int i)方法
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); //從i向下調整堆
if (queue[i] == moved) { // 如果發現調整後 moved 還在 i 位置沒有下沉，向上調整看是否上浮
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
堆插入元素與删除堆頂元素操作
以下面這個對為例
用數組來存儲為：
插入元素
往堆中插入一個元素後，需要繼續滿足堆的兩個特性，即：
（1）堆是一顆完全二叉樹；
（2）堆中某個節點的值總是不大于（或不小于）其父節點的值。
把元素插入到最後一層最後一個節點往後一位的位置，也就是在數組的末尾插入新的元素
，插入之後可能不再滿足條件（2），這時候我們需要調整，自下而上的堆化。
上面那個堆插入元素2，我們把它放在9後面，這時不滿足條件（2）了，我們就需要堆化。（這是一個小頂堆）
從插入元素的過程，我們知道每次與 n / ( 2 x ) n/(2^x) n/(2x) 的位置進行比較，是以，插入元素的時間複雜度為 O ( l o g n ) O(log n) O(logn)。
删除堆頂元素
删除了堆頂元素後，要使得還滿足堆的兩個特性。把最後一個元素移到根節點的位置，這時候就滿足條件（1），之後就需要堆化了使它滿足條件（2）
從删除元素的過程，我們知道把最後一個元素拿到根節點後，每次與 2 n 2n 2n 和 ( 2 n + 1 ) (2n+1) (2n+1) 位置的元素比較，取其小者，是以，删除元素的時間複雜度也為 O ( l o g n ) O(log n) O(logn) 。
回到 remove(Object o) 方法 ，不是删除堆頂元而是删除指定元素，源碼中會先找Object o在數組中位置 i，再取出最後一個元素從i自上而下堆化，如果最後一個元素沒有下沉，會從i自下而上堆化
參考：
拜托，面試别再問我堆（排序）了！
https://mp.weixin.qq.com/s/AF2tMHfofG8b51yIyaIReg