java中的priorityqueue是一种基于堆实现的优先队列，其核心特性是每次取出优先级最高的元素。1. 它提供了多种构造函数，包括默认容量和排序方式、指定容量、自定义比较器以及从集合初始化；2. 常用方法如offer/add插入元素、poll/remove移除元素、peek查看队首、size获取大小、contains检查是否存在，其中offer更安全，poll和remove时间复杂度为o(log n)，peek和size为o(1)，contains为o(n)；3. 可通过实现comparator接口自定义排序规则，并在构造时传入比较器；4. 与treeset不同，priorityqueue底层是堆，只保证队首有序，而treeset基于红黑树，所有元素有序且支持索引，但两者均不允许null元素，适用场景各有侧重。
Java中的PriorityQueue是一种特殊的队列，它允许我们按照元素的优先级来处理它们。简单来说，你可以把它想象成一个自动排序的队列，每次取出的是优先级最高的元素。
PriorityQueue的本质是一个堆（通常是小根堆），这意味着队列中的元素总是按照某种顺序排列，保证队首元素是最小（或最大，取决于你的比较器）。
解决方案
使用PriorityQueue的关键在于理解它的构造函数和常用方法。
立即学习“Java免费学习笔记（深入）”；
-
构造函数：
Android 开发者指南 第一部分：入门下载Android文档-开发者指南-第一部分：入门-中英文对照版 Android提供了丰富的应用程序框架，它允许您在Java语言环境中构建移动设备的创新应用程序和游戏。在左侧导航中列出的文档提供了有关如何使用Android的各种API来构建应用程序的详细信息。第一部分：Introduction(入门) 0、Introduction to Android(引进到Android) 1、Application Fundamentals(应用程序基础) 2、Device Compatibility(设备兼容性) 3、
-
PriorityQueue()：创建一个具有默认初始容量（11）的 PriorityQueue，并根据其元素的自然顺序对其进行排序。 -
PriorityQueue(int initialCapacity)：创建一个具有指定初始容量的 PriorityQueue，并根据其元素的自然顺序对其进行排序。 -
PriorityQueue(Comparator super E> comparator)：创建一个具有默认初始容量的 PriorityQueue，并根据指定的比较器对其元素进行排序。 -
PriorityQueue(int initialCapacity, Comparator super E> comparator)：创建一个具有指定初始容量的 PriorityQueue，并根据指定的比较器对其元素进行排序。 -
PriorityQueue(Collection extends E> c)：创建一个包含指定集合中的元素的 PriorityQueue。 -
PriorityQueue(PriorityQueue extends E> c)：创建一个包含指定优先级队列中的元素的 PriorityQueue。 -
PriorityQueue(SortedSet extends E> c)：创建一个包含指定排序集合中的元素的 PriorityQueue。
-
-
常用方法：
-
add(E e)/offer(E e)：将指定的元素插入此优先级队列。offer通常更安全，因为它在队列满时返回false而不是抛出异常。 -
peek()：检索但不移除此队列的头，如果此队列为空，则返回null。 -
poll()：检索并移除此队列的头，如果此队列为空，则返回null。 -
remove(Object o)：从此队列中移除指定元素的单个实例（如果存在）。 -
contains(Object o)：如果此队列包含指定元素，则返回true。 -
size()：返回此队列中的元素数量。 -
clear()：从此队列中移除所有元素。 -
iterator(): 返回在此队列中的元素上进行迭代的迭代器。
-
示例代码：
import java.util.PriorityQueue;
import java.util.Comparator;
public class PriorityQueueExample {
public static void main(String[] args) {
// 使用默认自然顺序的 PriorityQueue (小根堆)
PriorityQueue pq1 = new PriorityQueue<>();
pq1.add(5);
pq1.add(1);
pq1.add(10);
pq1.add(3);
System.out.println("Default PriorityQueue:");
while (!pq1.isEmpty()) {
System.out.print(pq1.poll() + " "); // 输出: 1 3 5 10
}
System.out.println();
// 使用自定义 Comparator 的 PriorityQueue (大根堆)
PriorityQueue pq2 = new PriorityQueue<>(Comparator.reverseOrder());
pq2.add(5);
pq2.add(1);
pq2.add(10);
pq2.add(3);
System.out.println("Custom Comparator PriorityQueue:");
while (!pq2.isEmpty()) {
System.out.print(pq2.poll() + " "); // 输出: 10 5 3 1
}
System.out.println();
// 使用自定义对象的 PriorityQueue
PriorityQueue taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));
taskQueue.add(new Task("Task A", 3));
taskQueue.add(new Task("Task B", 1));
taskQueue.add(new Task("Task C", 2));
System.out.println("Task PriorityQueue:");
while (!taskQueue.isEmpty()) {
System.out.println(taskQueue.poll());
}
}
static class Task {
private String name;
private int priority;
public Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
public String getName() {
return name;
}
public int getPriority() {
return priority;
}
@Override
public String toString() {
return "Task{" +
"name='" + name + '\'' +
", priority=" + priority +
'}';
}
}
} PriorityQueue 的时间复杂度是多少？
-
offer(E e)和add(E e): O(log n)，其中 n 是队列中的元素数量。这是因为插入元素后需要调整堆结构。 -
poll()和remove(Object o): O(log n)，其中 n 是队列中的元素数量。移除元素后也需要调整堆结构。 -
peek(): O(1)，因为只是查看堆顶元素，不需要调整堆。 -
size(): O(1)，直接返回队列的大小。 -
contains(Object o): O(n)，在最坏情况下需要遍历整个队列来查找元素。
如何自定义 PriorityQueue 的排序规则？
可以通过实现 Comparator 接口来定义自定义的排序规则。Comparator 接口允许你指定两个对象之间的比较方式。 在创建 PriorityQueue 实例时，将自定义的 Comparator 传递给构造函数。
import java.util.PriorityQueue;
import java.util.Comparator;
public class CustomPriorityQueue {
public static void main(String[] args) {
// 自定义 Comparator，按照字符串长度降序排列
Comparator stringLengthComparator = (s1, s2) -> s2.length() - s1.length();
PriorityQueue stringQueue = new PriorityQueue<>(stringLengthComparator);
stringQueue.add("apple");
stringQueue.add("banana");
stringQueue.add("kiwi");
stringQueue.add("orange");
System.out.println("Custom String PriorityQueue:");
while (!stringQueue.isEmpty()) {
System.out.println(stringQueue.poll()); // 输出: banana, orange, apple, kiwi
}
}
} PriorityQueue 和 TreeSet 的区别是什么？
PriorityQueue 和 TreeSet 都是用于存储有序元素的集合，但它们在实现和使用上有一些关键区别：
-
底层数据结构：
PriorityQueue基于堆（通常是小根堆）实现，而TreeSet基于红黑树实现。 -
排序方式：
PriorityQueue只保证队首元素是最小（或最大）的，其他元素的顺序不确定。TreeSet则保证所有元素都是有序的。 -
是否允许 null 元素：
PriorityQueue不允许存储null元素，会抛出NullPointerException。TreeSet也不允许存储null元素（在大多数实现中）。 -
时间复杂度：
PriorityQueue的offer和poll操作的时间复杂度为 O(log n)，peek操作为 O(1)。TreeSet的add、remove和contains操作的时间复杂度都为 O(log n)。 -
应用场景：
PriorityQueue适用于需要频繁获取最小（或最大）元素的场景，例如任务调度、堆排序等。TreeSet适用于需要维护有序集合的场景，例如字典、索引等。
简单来说，如果只需要获取优先级最高的元素，使用 PriorityQueue 效率更高。如果需要维护一个完全有序的集合，使用 TreeSet 更合适。
