Java 優先級隊列

教學
Java

有時我們需要按照特定的順序處理隊列中的項目。優先級隊列是一種執行此任務的數據結構。Java優先級隊列不同於“普通”的隊列。它不是按照先進先出的順序檢索項目，而是按照它們的優先級順序檢索。

Java優先級隊列

java.util.PriorityQueue類為我們提供了這樣一種數據類型的實現，它在內部使用優先級堆實現。Java優先級隊列是一個無界隊列。它在Java 1.5中引入並在Java SE 8版本中進行了增強。PriorityQueue內部通過以下“優先級堆”數據結構來實現。這是PriorityQueue類的層次結構： PriorityQueue類圖：

Java優先級隊列構造函數

  1. PriorityQueue() – 使用默認初始容量（即11）創建優先級隊列
  2. PriorityQueue(Collection c) – 使用指定集合中的元素創建優先級隊列
  3. PriorityQueue(int initialCapacity) – 使用指定的初始容量創建 PriorityQueue
  4. PriorityQueue(int initialCapacity, Comparator comparator) – 使用提供的初始容量創建 PriorityQueue，其元素的排序依據指定的比較器
  5. PriorityQueue(PriorityQueue c) – 創建包含指定優先級佇列中元素的 PriorityQueue
  6. PriorityQueue(SortedSet c) – 創建包含指定排序集合中元素的 PriorityQueue

優先級佇列元素按其自然順序排序，除非我們在創建時提供了 Comparator。元素默認按升序排序，因此佇列的頭部是優先級最低的元素。如果有兩個元素在同一時間有資格成為頭部，這種情況下的順序是隨機的。

Java 優先級佇列範例

讓我們創建一個包含各種任務的 PriorityQueue：

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

這將創建一個以 String 的自然排序為基準的 PriorityQueue。讓我們再創建一個以自然排序的相反順序排序任務的 PriorityQueue。因此，我們需要傳遞一個比較器：

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java PriorityQueue 方法

現在，讓我們來看一下 PriorityQueue 中所有可用的方法並使用它們：

  1. Boolean add(E e) – 此方法將指定的元素插入隊列中。我們已經使用此方法在我們的隊列中添加了 5 個任務。

  2. Comparator comparator() – 此方法返回用於排序此隊列中元素的比較器。如果未指定比較器且隊列根據其元素的自然順序進行排序，則返回 null。因此，如果我們執行：

    System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

    輸出將是：

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – 如果隊列包含指定的元素，則返回true。讓我們檢查“task3”是否屬於優先隊列tasks：

    System.out.println(tasks.contains("task3"));

    這會打印出：

    true

  4. boolean offer(E e) – 就像add()方法一樣，此方法也把一個元素添加到隊列中。對於容量受限的隊列，offer()和add()方法實際上有些不同，但在優先隊列的情況下，兩者是相同的。與add()不同，即使無法將元素添加到隊列中，offer()也不會拋出異常。

  5. E peek() – 檢索此隊列的頭部，或者如果此隊列為空，則返回null。換句話說，它返回最高優先級的元素。所以下面的代碼：

    System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

    給我們：

    task1
task5

  6. E poll() – 此方法也檢索佇列的頭部（具有最高優先級的元素），如果佇列為空則返回 null。但與 peek() 不同的是，它還會刪除該元素。因此，如果我們調用 poll()：

    System.out.println(“在 tasks 上進行 Poll: ”+tasks.poll());
System.out.println(“在 reverseTasks 上進行 Poll: ”+reverseTasks.poll());

    然後 peek：

    System.out.println(“在 tasks 上進行 Peek: ”+tasks.peek());
System.out.println(“在 reverseTasks 上進行 Peek: ”+reverseTasks.peek());

    我們將獲得以下輸出：

    在 tasks 上進行 Poll: task1
在 reverseTasks 上進行 Poll: task5
在 tasks 上進行 Peek: task2
在 reverseTasks 上進行 Peek: task4

  7. int size() – 返回佇列中的元素數量。

  8. boolean remove(Object o) – 如果存在，從佇列中刪除指定的元素。如果存在兩個相同的元素，則只刪除其中一個。

  9. Object[] toArray() – 返回包含佇列中所有元素的數組。

  10. T[] toArray(T[] a) – 將佇列中所有元素轉換為陣列，返回的陣列類型與指定的陣列相同。

  11. Iterator iterator() – 返回佇列的迭代器。

  12. void clear() – 從佇列中刪除所有元素。

除了這些方法外，PriorityQueue 還繼承自 Collection 和 Object 類別的方法。

Java PriorityQueue 時間複雜度

  1. 對於入隊和出隊方法，時間複雜度為 O(log(n))
  2. 對於 remove(Object) 和 contains(Object) 方法，時間複雜度為線性的
  3. 對於檢索方法，具有常數時間複雜度

此優先佇列實現並非線程安全。因此，如果需要同步訪問，應使用 PriorityBlockingQueue。參考：API 文檔

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java