PriorityQueue源碼分析

重點知識羅列

• PriorityQueue 采用數組的形式儲存資料，邏輯上采用二叉堆儲存

  有關二叉堆的實作原理，檢視本人博文 Ted 帶你學習資料結構 之 二叉堆

• PriorityQueue 數組排序并非按照插入順序，而是需要根據比較器判斷; 插入自定義對象時，自定義對象需要實作Comparable接口 ，或者使用外部比較器對象，外部比較器對象需實作Compartor接口

  關于比較器詳細介紹，可參考本人博文ompareable接口和Compartor接口對比分析

• PriorityQueue 不能加入null值
• PriorityQueue 插入和删除原理代碼實作

代碼選取jdk1.8

① PriorityQueue 屬性

private static final int DEFAULT_INITIAL_CAPACITY = 11;

transient Object[] queue;

private int size = 0;

private final Comparator<? super E> comparator;
  
transient int modCount = 0;  
           

由上可知 ： PriorityQueue 裡面維護了一個Object數組對象 ，且默大小為11

② 構造器

public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity,
 Comparator<? super E> comparator) {

if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
} 
           

由上可知： 構造一個 PriorityQueue對象，按照預設11個尺寸建立Object[] 數組，且如果沒有傳入比較器Comparator對象，為null ;

③ 添加對象

public boolean add(E e) {
return offer(e);
}

 public boolean offer(E e) {
if (e == null)
throw new NullPointerException();  // 這是該對象不能加入null值最好例證
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;
}  
           

上面方法中，主要調了grow（）方法，和sitUp（）方法，我們深入研究下

private void grow(int minCapacity) {
int oldCapacity = queue.length;

int newCapacity = oldCapacity + ((oldCapacity < 64) ?
 (oldCapacity + 2) :
 (oldCapacity >> 1));  

 // 當小于64時，表示堆高在6層内時，每次擴容為原來的1倍+2 ，當大于6層時，每次擴容原來的50%    
 // 層高計算方式為 H=log(Length) ,但當length為2的次方時，H=log(Length)+1
 //上面64，因為是2的6次方，代入到公式中為log64+1 =7,但為為是<号，是以實則表示6層，未到7層

if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
} 
           

private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
} 
           

siftUp（）方法，需要判斷有沒有比較器，我們就以siftUpUsingComparator(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-1)>>>1，位移運算符，獲得父節點的索引，然後得到它的值 Object e ,比較父節點e和傳入的對象x,如果，子節點比父節點大，那麼，break跳出while循環 ; 但如果子節點值不如父節點，那麼，它們的值交換位置，并且，此時，仍在while循環裡面，會層層和父節點比較，如果發生父節點比子節點大的情況，會一直交換值，直到對象x，到達堆頂

（4）删除對象

poll方法的原理， 從堆頂冊除對象a，并且堆中最末位b對象替換堆頂值，然後下沉排序，（拿到根節點下的左右節點，并且判斷左右節點的大小，b如果值>子節點，和子節點中中最小值進行替換，循環）

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 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;
} 
           

（5）取值

public E peek() {
return (size == 0) ? null : (E) queue[0];
}
           

取值方法，很好了解了，就是拿到堆頂的值。