Java 優先級隊列：不是經典隊列

在本文中，我們學習了一個優先級隊列，Java 類，它實現了 Queue 接口。程序員對常規隊列接口了解多少？首先，該接口基於 FIFO 原則或“先進先出”。這提醒了普通隊列中的常規隊列。你想從 McDrive 買咖啡嗎？如果您的車是靠近窗戶的第一個，您將在下一個司機之前拿到咖啡。

隊列接口聲明

public interface Queue<E> extends Collection<E>

什麼是優先隊列

什麼是優先隊列？首先，它是一個實現 Queue 接口的類，以防從後面插入一個元素並從頭部移除一個元素。然而，它不是一個通常的內部隊列。Java 優先級隊列元素的順序取決於元素的優先級。具有最高優先級的元素將被移動到隊列的頭部。如果您刪除（提供）排名最高的元素，則第二個元素會走到頭去喝咖啡。優先級是如何確定的？根據文檔，優先級隊列的元素根據它們的自然順序進行排序，或者由隊列構造時提供的比較器排序，具體取決於使用的​​構造函數。基於優先級最小堆的優先級隊列。這意味著，在數字隊列元素的情況下，隊列的第一個元素將是這些數字中的最小值。很多新手學生在閱讀這個定義後開始認為優先級隊列是線性排序的。也就是說，如果我們使用一個元素為自然數的隊列，那麼第一個元素將是最小的，而最後一個元素將是最大的。這不完全正確。要了解優先級隊列實際上是如何工作的以及它提供了什麼，您需要弄清楚堆是如何工作的。稍後我們將使用一個示例來考慮優先級隊列的內部結構。現在讓我們詳細討論它的外部屬性。那麼第一個元素將是最小的，最後一個元素將是最大的。這不完全正確。要了解優先級隊列實際上是如何工作的以及它提供了什麼，您需要弄清楚堆是如何工作的。稍後我們將使用一個示例來考慮優先級隊列的內部結構。現在讓我們詳細討論它的外部屬性。那麼第一個元素將是最小的，最後一個元素將是最大的。這不完全正確。要了解優先級隊列實際上是如何工作的以及它提供了什麼，您需要弄清楚堆是如何工作的。稍後我們將使用一個示例來考慮優先級隊列的內部結構。現在讓我們詳細討論它的外部屬性。

PriorityQueue 類構造函數和聲明

PriorityQueue 類提供了 6 種不同的方法來在 Java 中構建優先級隊列。

• PriorityQueue() - 具有默認初始容量 (11) 的空隊列，它根據元素的自然順序對其元素進行排序。
• PriorityQueue(Collection c) - 包含指定集合中的元素的空隊列。
• PriorityQueue(int initialCapacity) - 具有指定初始容量的空隊列，根據元素的自然順序對其元素進行排序。
• PriorityQueue(int initialCapacity, Comparator comparator) - 具有指定初始容量的空隊列，它根據指定的比較器對其元素進行排序。
• PriorityQueue(PriorityQueue c) - 包含指定優先級隊列中元素的空隊列。
• PriorityQueue(SortedSet c) - 包含指定排序集中元素的空隊列。

Java 中的優先級隊列的聲明方式如下：

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

創建優先隊列

讓我們創建一個整數優先級隊列。優先隊列實現，Java代碼：

PriorityQueue<Integer> numbers = new PriorityQueue<>();

我們創建了一個沒有參數的優先級隊列。在這種情況下，優先隊列的頭部是隊列的最小編號。如果你移除頭部，下一個最小的元素將佔據這個位置。所以你可以按升序從隊列中移除元素。如有必要，您可以使用 Comparator 接口更改排序原則。

Java 優先隊列方法

PriorityQueue Java 類具有添加、刪除和檢查元素的重要方法。

將元素插入優先隊列

• boolean add(object)將指定的元素插入到優先級隊列中。成功時返回真。如果隊列已滿，該方法將拋出異常。
• boolean offer(object)將指定元素插入此優先級隊列。如果隊列已滿，則該方法返回 false。

您可以使用這兩種添加操作，大多數情況下沒有區別。這是一個啟動和添加元素到優先級隊列的小例子。

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

輸出是：

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

元素的排列順序好像很奇怪，後面再解釋。

從優先隊列中檢索和刪除元素

• boolean remove(object)從此隊列中移除指定元素的單個實例（如果存在）。
• 對象 poll()檢索並刪除此隊列的頭部。如果隊列為空，則返回 null。
• void clear()從優先級隊列中刪除所有元素。
• Object element()檢索此隊列的頭部而不刪除它。如果隊列為空，則拋出NoSuchElementException 。
• 對象 peek()檢索隊列的頭部而不刪除它。如果隊列為空，則返回 null。

import java.util.PriorityQueue;
import java.util.Queue;

public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

輸出：

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

如您所見，嘗試使用 element() 方法打印出空隊列的頭部會導致NoSuchElementexception。

優先隊列比較器

• Comparator comparator()返回用於對隊列中的元素進行排序的比較器。如果隊列是根據其元素的自然順序排序的，則返回 null。

Java 優先級隊列，帶有比較器的示例

我們在上面的代碼示例中使用了自然（升序）順序，但有時我們應該更改它。這是 Java 優先級隊列示例，我們在其中創建自己的內部比較器類來實現 Comparator 接口。我們的比較器將從最大到最小對元素進行排序。

import java.util.PriorityQueue;
import java.util.Comparator;

class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

輸出：

the head of Queue = 5
5
4
3
2
1

Queue 的頭部現在不是最小元素，而是最大元素，並且順序被改成了相反的。

使用迭代器遍歷 PriorityQueue

ProrityQueue 是 Collection 框架的一部分，實現了Iterable<>接口。要迭代優先級隊列的元素，您可以使用iterator()方法。這是一個例子：

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;

class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

輸出：

1 2 4 5 3

更多 PriorityQueue 方法

• 如果隊列包含 o 元素，則boolean contains(Object o)返回 true。
• int size()返回此隊列中的元素數。
• Object[] toArray()返回一個包含此隊列中所有元素的數組。

這是一個例子：

import java.util.PriorityQueue;
import java.util.Queue;

public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }

       System.out.println("our queue: " + priorityQueue);

       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));

       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

輸出：

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8 定義

如果您打開 priorityqueue java 8 文檔，您會發現下一個定義：基於優先級堆的無界優先級隊列。優先級隊列的元素根據它們的自然順序進行排序，或者由隊列構造時提供的比較器排序，具體取決於使用的​​構造函數。優先隊列不允許空元素。依賴自然排序的優先級隊列也不允許插入不可比較的對象（這樣做可能會導致 ClassCastException）。堆在這裡是一個非常重要的詞。它解釋了優先隊列元素排序的屬性。

PriorityQueue工作原理：二叉堆

讓我們從一個例子開始。讓我們創建兩個實現 Queue 接口的對象。其中之一是 LinkedList，第二個是 PriorityQueue。它們都有 5 個 Integer 元素（1、2、3、4 和 5），我們開始將元素從大到小放入我們的隊列中。所以，第一個是 5，然後是 4、3、2，最後一個是 1。然後打印出兩個列表以檢查順序。

Queue<Integer> queueL = new LinkedList<>();
    for (int i = 5; i > 0; i--) {
        queueL.add(i);
    }
    System.out.println("LinkedList Queue (FIFO): " + queueL);
    Queue<Integer> priorityQueue = new PriorityQueue<>();

    for (int i = 5; i > 0; i--) {
    priorityQueue.offer(i);
    }
    System.out.println("PriorityQueue: " + priorityQueue)

這些代碼工作的結果是下一個：

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

好吧，鍊錶順序是可以預測和理解的。按照先進先出原則排序。我們從 5 開始，所以這個元素排在第一位，然後是 4，依此類推。關於優先隊列順序，我們能說些什麼？文檔說優先級隊列的元素是根據它們的自然順序排序的，或者由隊列構造時提供的比較器排序。然而，這種順序在線性排序的意義上似乎並不“自然”。我們寧願期望 [1, 2, 3, 4, 5]，而不是 [1, 2, 4, 5, 3]。要理解為什麼檢索順序是這樣，我們應該回憶一下基於堆的優先級隊列。什麼是堆？它是一種基於二叉樹的數據結構. 堆的主要性質：每個父堆的優先級大於其子堆的優先級。讓我提醒您，如果每個父母的孩子不超過兩個，並且級別的填充從上到下（從同一級別 - 從左到右），則樹稱為完全二叉樹。每次向其中添加或刪除元素時，二叉堆都會自行重組。在最小堆的情況下，無論插入順序如何，最小的元素都會進入根。基於這個最小堆的優先級隊列。這意味著，在數字隊列元素的情況下，隊列的第一個元素將是這些數字中的最小值。如果刪除根，則下一個最小的成為根。

讓我們回到我們的例子。

第 1 步。我們將“5”放入優先級隊列。它成為根。 第 2 步。我們將“4”添加到優先級隊列中。4 <5，所以新元素應該比舊元素高。4 成為一個根，5 是它的左孩子。現在Java中的數據結構是[4, 5] 第三步，我們加'3'。暫時它成為根 (4) 的右孩子。但是，3 < 4，所以我們應該把它抬高。交換 3 和 4。現在我們有一個結構，例如 [3, 5, 4] 步驟 4.我們添加“2”。變成5的左孩子。2<5，所以交換它們。2變成了3的左孩子，2 < 3，所以又多了一個交換過程。現在我們有一個結構 [2,3,4,5] 第 5 步。我們加'1'。它從 3 的右孩子到 2 的左孩子，然後到根。結果數據結構：[1,2,4,5,3] Removal 過程從根開始，並引發反向過程。所以，首先我們有 1 作為根，然後是 2、3、4，最後是 5。這就是使用刪除操作 poll() 的原因

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

我們在線性輸出中得到了“排序”：

1
2
3
4
5

所以優先級隊列對於某些操作可能是有效的。插入和刪除每個元素需要O(log N)的時間，你可以在O(1)中得到最小的元素。這是完整的例子：

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

重要的是要了解優先級隊列是基於二叉堆的，因此它們不會使元素保持線性排序。從根到葉的每條路都是有序的，但從根到不同的路則不是。這意味著您可以非常快速地獲取隊列的最小元素。

關於優先級隊列你應該知道的。簡要清單

• 優先隊列不允許 NULL 對象。
• 您只能將可比較的對象添加到 PriorityQueue 中。
• 優先級隊列構建為最小堆，一種二叉樹。最小元素是根。優先級隊列的對象默認按自然順序排列。
• 如果需要自定義排序，可以使用 Comparator。
• PriorityQueue 不是線程安全的，因此您最好使用 PriorityBlockingQueue 在並發環境中工作。
• PriorityQueue 為添加和輪詢方法提供 O(log(n)) 時間，為獲取最少的元素提供 O(1) 時間。