CodeGym /Java Blog /Toto sisi /Java 優先級隊列:不是經典隊列
John Squirrels
等級 41
San Francisco

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

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

隊列接口聲明


public interface Queue<E> extends Collection<E>

什麼是優先隊列

Java 優先級隊列:不是經典隊列 - 2什麼是優先隊列?首先,它是一個實現 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] Java 優先級隊列:不是經典隊列 - 3Removal 過程從根開始,並引發反向過程。所以,首先我們有 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) 時間。
留言
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION