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