細說 PriorityQueue

PriorityQueue 的用法在網路上有很多資料可以查詢，這裡就不在介紹，
想在這裡說明的是 PriorityQueue 的實作以及要小心避免的錯誤使用方式。
PriorityQueue 如同它的名字一般，多了 Priority 的功能，
在做 offer 的時候會依據物件的 Priority 來加進 Queue 裡，
這裡出現了第一個要注意的地方，有越小 Priority 的物件是排在比較前面的，
也就是說當你透過 poll 來取得物件時，拿到的是當中最小的那個。
那如果想要取得的是 Priority 最大的怎麼辦?
有兩個方法，二擇一:

1. 把有較大 Priority 的物件，定義較小的比較值。
2. compare(T o1, T o2) 方法的結果反過來就行了。
   通常我們說當 o1 > o2 時，應該要回傳 > 0，這樣的結果 PriorityQueue 的排序就會是遞增的。如果想要遞減，當 o1 > o2 時，回傳 < 0 就行了。

PriorityQueue 其實是用最小堆積樹(Min Heap Tree)來實作的，從 source code 可以看出端倪:
k = size-1，x = 要插任的物件

587  private void siftUp(int k, E x) {
588      if (comparator != null)
589          siftUpUsingComparator(k, x);
590      else
591          siftUpComparable(k, x);
592  }
594  private void siftUpComparable(int k, E x) {
595      Comparable<? super E> key = (Comparable<? super E>) x;
596      while (k > 0) {
597          int parent = (k - 1) >>> 1;
598          Object e = queue[parent];
599          if (key.compareTo((E) e) >= 0)
600              break;
601          queue[k] = e;
602          k = parent;
603      }
604      queue[k] = key;
605  }
607  private void siftUpUsingComparator(int k, E x) {
608      while (k > 0) {
609          int parent = (k - 1) >>> 1;
610          Object e = queue[parent];
611          if (comparator.compare(x, (E) e) >= 0)
612              break;
613          queue[k] = e;
614          k = parent;
615      }
616      queue[k] = x;
617  }

每次做 offer 時，都會呼叫 siftUp 來把物件加到樹中，過程如下圖所示:



而每次做 poll 時，都會呼叫 siftDown 來重新排序物件，過程如下圖所示:
k = 0，x = 最後一個物件

627  private void siftDown(int k, E x) {
628      if (comparator != null)
629          siftDownUsingComparator(k, x);
630      else
631          siftDownComparable(k, x);
632  }
634  private void siftDownComparable(int k, E x) {
635      Comparable<? super E> key = (Comparable<? super E>)x;
636      int half = size >>> 1;        // loop while a non-leaf
637      while (k < half) {
638          int child = (k << 1) + 1; // assume left child is least
639          Object c = queue[child];
640          int right = child + 1;
641          if (right < size &&
642              ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
643              c = queue[child = right];
644          if (key.compareTo((E) c) <= 0)
645              break;
646          queue[k] = c;
647          k = child;
648      }
649      queue[k] = key;
650  }
652  private void siftDownUsingComparator(int k, E x) {
653      int half = size >>> 1;
654      while (k < half) {
655          int child = (k << 1) + 1;
656          Object c = queue[child];
657          int right = child + 1;
658          if (right < size &&
659              comparator.compare((E) c, (E) queue[right]) > 0)
660              c = queue[child = right];
661          if (comparator.compare(x, (E) c) <= 0)
662              break;
663          queue[k] = c;
664          k = child;
665      }
666      queue[k] = x;
667  }

第二個要注意的點來了!
已經加進 PriorityQueue 的物件可以隨意更動 Priority 嗎?
答案是 NO!!
隨意更動物件的 Priority，就破壞了原本樹的排序，接下來不管是 offer 或 poll 可能都是錯誤的結果。
此外，同樣 Priority 的物件是不保證順序的!