Java中的PriorityQueue

什么是Java中的PriorityQueue？

队列遵循先进先出（First-In-First-Out）算法，而PriorityQueue的队列元素则根据优先级进行处理（按自然顺序或根据创建时提供的自定义比较器排序）。PriorityQueue基于优先级堆。我们无法创建不可比较对象的PriorityQueue。向PriorityQueue插入null将抛出NullPointerException，因为Java中的PriorityQueue不允许null元素。PriorityQueue是无界队列。此队列的头是相对于指定排序的最小元素。如果多个元素的值相同，则头是这些元素中的一个——平局将任意打破。队列检索操作poll、remove、peek和element访问队列头部的元素。PriorityQueue从AbstractQueue、AbstractCollection、Collection和Object类继承方法。在PriorityQueue中插入元素（offer()）和删除元素（poll()）的时间复杂度均为O(log n)，其中n是队列中的元素数量。默认的PriorityQueue使用最小堆实现，这意味着堆中的顶部元素是最小的。如果我们想实现最大堆，则需要使用自定义比较器。在内部，Java中的PriorityQueue使用数组存储元素。如果初始容量（在JDK 17中默认是11）不足以容纳所有添加到队列中的元素，则该数组会自动增大。虽然在创建PriorityQueue时不必指定初始容量，但如果您知道将要添加的元素数量，设置初始容量是有益的。这有助于防止队列频繁调整大小，从而避免浪费CPU资源。

您能提供一个PriorityQueue有用的示例场景吗？

PriorityQueue可以用于操作系统中的任务调度等场景，在这些场景中，具有更高优先级的任务需要在较低优先级的任务之前执行。

PriorityQueue构造函数

• PriorityQueue()：创建一个具有默认初始容量（11）的PriorityQueue，该队列根据自然顺序对其元素进行排序。
• PriorityQueue(Collection c)：创建一个包含指定集合中元素的PriorityQueue。
• PriorityQueue(int initialCapacity)：创建一个具有指定初始容量的PriorityQueue，该队列根据自然顺序对其元素进行排序。
• PriorityQueue(int initialCapacity, Comparator comparator)：创建一个具有指定初始容量的PriorityQueue，该队列根据指定比较器对其元素进行排序。
• PriorityQueue(PriorityQueue c)：创建一个包含另一个优先队列中元素的PriorityQueue。
• PriorityQueue(SortedSet c)：创建一个包含指定排序集中的元素的PriorityQueue。

PriorityQueue操作

• boolean add(E element)：将指定元素插入此优先队列。
• boolean offer(E e)：用于将特定元素插入优先队列。
• public peek()：检索但不移除此队列的头部，若队列为空则返回null。
• public poll()：检索并移除此队列的头部，若队列为空则返回null。
• public remove()：从此队列中移除指定元素的单个实例（如果存在）。当我们从优先队列中移除元素时，首先移除的是按照指定顺序的最小元素。
• Iterator iterator()：返回此队列中元素的迭代器。
• boolean contains(Object o)：若此队列包含指定元素则返回true。
• void clear()：用于移除优先队列的所有内容。
• int size()：返回集合中存在的元素数量。
• toArray()：用于返回一个包含此队列中所有元素的数组。
• Comparator comparator()：用于返回可以用于排序队列元素的比较器。

offer和add方法的区别是什么？

offer()和add()是两种将数据插入PriorityQueue的方法。在队列中，add用于将指定元素插入队列。成功时返回true，否则抛出异常。offer()也用于将指定元素插入队列，但成功时返回true，否则返回false。在PriorityQueue的情况下，add方法的行为与offer()相同。如果查看实现，PriorityQueue的add方法内部调用了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技能，可关注我们的Java培训课程。