Java中的PriorityQueue

什么是Java中的PriorityQueue？

隊(duì)列遵循先進(jìn)先出（First-In-First-Out）算法，而PriorityQueue的隊(duì)列元素則根據(jù)優(yōu)先級(jí)進(jìn)行處理（按自然順序或根據(jù)創(chuàng)建時(shí)提供的自定義比較器排序）。PriorityQueue基于優(yōu)先級(jí)堆。我們無(wú)法創(chuàng)建不可比較對(duì)象的PriorityQueue。向PriorityQueue插入null將拋出NullPointerException，因?yàn)镴ava中的PriorityQueue不允許null元素。PriorityQueue是無(wú)界隊(duì)列。此隊(duì)列的頭是相對(duì)于指定排序的最小元素。如果多個(gè)元素的值相同，則頭是這些元素中的一個(gè)——平局將任意打破。隊(duì)列檢索操作poll、remove、peek和element訪問(wèn)隊(duì)列頭部的元素。PriorityQueue從AbstractQueue、AbstractCollection、Collection和Object類(lèi)繼承方法。在PriorityQueue中插入元素（offer()）和刪除元素（poll()）的時(shí)間復(fù)雜度均為O(log n)，其中n是隊(duì)列中的元素?cái)?shù)量。默認(rèn)的PriorityQueue使用最小堆實(shí)現(xiàn)，這意味著堆中的頂部元素是最小的。如果我們想實(shí)現(xiàn)最大堆，則需要使用自定義比較器。在內(nèi)部，Java中的PriorityQueue使用數(shù)組存儲(chǔ)元素。如果初始容量（在JDK 17中默認(rèn)是11）不足以容納所有添加到隊(duì)列中的元素，則該數(shù)組會(huì)自動(dòng)增大。雖然在創(chuàng)建PriorityQueue時(shí)不必指定初始容量，但如果您知道將要添加的元素?cái)?shù)量，設(shè)置初始容量是有益的。這有助于防止隊(duì)列頻繁調(diào)整大小，從而避免浪費(fèi)CPU資源。

您能提供一個(gè)PriorityQueue有用的示例場(chǎng)景嗎？

PriorityQueue可以用于操作系統(tǒng)中的任務(wù)調(diào)度等場(chǎng)景，在這些場(chǎng)景中，具有更高優(yōu)先級(jí)的任務(wù)需要在較低優(yōu)先級(jí)的任務(wù)之前執(zhí)行。

PriorityQueue構(gòu)造函數(shù)

• PriorityQueue()：創(chuàng)建一個(gè)具有默認(rèn)初始容量（11）的PriorityQueue，該隊(duì)列根據(jù)自然順序?qū)ζ湓剡M(jìn)行排序。
• PriorityQueue(Collection c)：創(chuàng)建一個(gè)包含指定集合中元素的PriorityQueue。
• PriorityQueue(int initialCapacity)：創(chuàng)建一個(gè)具有指定初始容量的PriorityQueue，該隊(duì)列根據(jù)自然順序?qū)ζ湓剡M(jìn)行排序。
• PriorityQueue(int initialCapacity, Comparator comparator)：創(chuàng)建一個(gè)具有指定初始容量的PriorityQueue，該隊(duì)列根據(jù)指定比較器對(duì)其元素進(jìn)行排序。
• PriorityQueue(PriorityQueue c)：創(chuàng)建一個(gè)包含另一個(gè)優(yōu)先隊(duì)列中元素的PriorityQueue。
• PriorityQueue(SortedSet c)：創(chuàng)建一個(gè)包含指定排序集中的元素的PriorityQueue。

PriorityQueue操作

• boolean add(E element)：將指定元素插入此優(yōu)先隊(duì)列。
• boolean offer(E e)：用于將特定元素插入優(yōu)先隊(duì)列。
• public peek()：檢索但不移除此隊(duì)列的頭部，若隊(duì)列為空則返回null。
• public poll()：檢索并移除此隊(duì)列的頭部，若隊(duì)列為空則返回null。
• public remove()：從此隊(duì)列中移除指定元素的單個(gè)實(shí)例（如果存在）。當(dāng)我們從優(yōu)先隊(duì)列中移除元素時(shí)，首先移除的是按照指定順序的最小元素。
• Iterator iterator()：返回此隊(duì)列中元素的迭代器。
• boolean contains(Object o)：若此隊(duì)列包含指定元素則返回true。
• void clear()：用于移除優(yōu)先隊(duì)列的所有內(nèi)容。
• int size()：返回集合中存在的元素?cái)?shù)量。
• toArray()：用于返回一個(gè)包含此隊(duì)列中所有元素的數(shù)組。
• Comparator comparator()：用于返回可以用于排序隊(duì)列元素的比較器。

offer和add方法的區(qū)別是什么？

offer()和add()是兩種將數(shù)據(jù)插入PriorityQueue的方法。在隊(duì)列中，add用于將指定元素插入隊(duì)列。成功時(shí)返回true，否則拋出異常。offer()也用于將指定元素插入隊(duì)列，但成功時(shí)返回true，否則返回false。在PriorityQueue的情況下，add方法的行為與offer()相同。如果查看實(shí)現(xiàn)，PriorityQueue的add方法內(nèi)部調(diào)用了offer。

PriorityQueue示例

import java.util.Iterator;
import java.util.PriorityQueue;
public class PriorityQueueDemo {
public static void main(String[] args) {
		
		PriorityQueue<String> pQueue = new PriorityQueue<>();
		pQueue.add("Sebastian");
		pQueue.add("Boguslaw");
		pQueue.add("Kazimierz ");
		pQueue.add("Bozena");
		System.out.println("Size of pQueue:" + pQueue.size()); // 4
		Object[] arr = pQueue.toArray();
		System.out.println("Coverting pQueue into Array: ");
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i].toString() + ", ");// Boguslaw, Bozena, Kazimierz , Sebastian,
		System.out.println();
		Iterator<String> pqItr = pQueue.iterator();
		while (pqItr.hasNext())
			System.out.print(pqItr.next() + ", ");// Boguslaw, Bozena, Kazimierz, Sebastian,
		System.out.println();
		pQueue.remove("Bozena");
		System.out.println("Printing pQueue after removing Bozena");
		pqItr = pQueue.iterator();
		while (pqItr.hasNext())
			System.out.print(pqItr.next() + ", ");// Boguslaw, Kazimierz , Sebastian,
		boolean isPresent = pQueue.contains("Bozena");
		System.out.println("pQueue contains Bozena or not? " + isPresent); // false
		
		isPresent = pQueue.contains("Sebastian");
		System.out.println("pQueue contains Sebastian or not? " + isPresent); // true
		System.out.println("Head of pQueue from peek:" + pQueue.peek());// Boguslaw
		System.out.println("Head of pQueue from poll:" + pQueue.poll());// Boguslaw
		pqItr = pQueue.iterator();
		while (pqItr.hasNext())
			System.out.print(pqItr.next() + ", ");// Kazimierz , Sebastian,
		System.out.println();
		pQueue.clear();
		System.out.println("Size of pQueue after calling clear:" + pQueue.size()); // 0
	}	
}

若你想提升Java技能，可關(guān)注我們的Java培訓(xùn)課程。