Java 最大優先順序佇列

在 Java 中建立最大優先佇列時，請建立一個搭配比較器的 PriorityQueue，讓比較器反轉值的自然排序。如此一來，佇列的頂端就是最大元素；重複呼叫 poll() 會依照從大到小的順序移除元素。Java 預設的 PriorityQueue 是最小堆積，因此若未提供比較器，頂端會是最小元素。

Java 中的優先佇列是什麼

優先佇列會依照優先順序取出元素，而非按照插入順序。它不是 FIFO 佇列：如果後插入的元素優先順序較高，就可能比其他元素先取出。使用自然排序時，優先順序依據值的 Comparable 順序；有其他排序需求時，則可由比較器指定。

Java 的 PriorityQueue 以堆積為基礎，能有效率地存取頂端元素。新增與移除元素需要對數時間；使用 peek() 查看頂端則需要常數時間。這個類別不是執行緒安全的。若要在並行環境中使用，可考慮 java.util.concurrent 中的 PriorityBlockingQueue，並留意它有不同的並行處理行為。

Java 的 PriorityQueue 如何排序元素

排序規則決定哪個元素位於佇列頂端。使用預設建構子時，整數與字串會採用自然排序，因此最小值位於頂端。比較器可以反轉這個順序，也可以比較自訂物件中的欄位。

堆積不會讓所有元素都維持排序後的順序。迭代器會走訪堆積的內部結構，因此迭代 PriorityQueue 不保證輸出結果已排序。若要查看目前的頂端，請使用 peek()；若要依優先順序取得元素，則重複移除頂端。

為自然排序的值建立最大優先佇列

對整數值傳入一個以右運算元和左運算元進行比較的比較器即可。同樣的做法也適用於字串等其他具有自然排序的值。元素插入時，佇列會依照比較器安排頂端；不必先排序輸入值。

以下範例示範這種做法：

本節中的程式碼以及顯示的標籤或輸出仍為英文。

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> values = new PriorityQueue<>((left, right) -> {
            if (left < right) return 1;
            if (left > right) return -1;
            return 0;
        });
        values.add(20);
        values.add(10);
        values.add(30);

        System.out.println(values.poll());
        System.out.println(values.poll());
        System.out.println(values.poll());
    }
}

比較分支會反轉整數的自然排序，且不會以相減方式比較值；極大或極小的整數相減可能造成溢位。依照這個比較器，佇列頂端會是最大值。每次呼叫 poll() 都會移除頂端，因此清空佇列時會依照遞減順序取得值。

對字串而言，可以使用 right.compareTo(left) 反轉其自然字典順序。也就是說，「最大」由值型別的排序規則決定；除非比較器另有定義，否則它不代表最長字串或符合特定領域需求的排名。

依優先順序排列自訂物件

自訂物件可以依其中一個欄位排序。例如，若 Task 有整數 priority，可用明確的小於與大於分支，比較右側工作與左側工作的優先值；相等時則回傳零。這樣較大的優先值會排在頂端，而且不需要用算術相減比較。

比較器必須保持一致：若兩個物件的優先值被判定為相等，任一個都可能先取出。優先佇列不保證相同優先值的元素會依穩定順序排列。若應用程式需要明確決定同優先值工作項目的順序，可以加入次要比較條件，例如序號。

取得最大元素並避免排序上的陷阱

使用 peek() 查看最大值但不移除它；使用 poll() 移除並回傳目前的最大值。佇列為空時，peek() 和 poll() 都會回傳 null；請檢查回傳值是否為 null，或先檢查 isEmpty()，再使用取得的值。重複呼叫 poll()，直到回傳 null，就會依比較器順序清空佇列。

不要把迭代當成排序後的走訪方式，也不要說佇列本身已排序。比較器會決定頂端元素以及後續的移除順序。建立最大優先佇列時，請安全地反轉自然排序或欄位排序；若多個執行緒需要修改此結構，請使用支援並行操作的佇列實作。