PriorityQueue概述
PriorityQueue` 是 Java 中的一个数据结构，它是一个优先队列实现，可以用来存储一组元素，并根据其优先级进行排序和检索。优先队列是一种特殊的队列，其中元素被赋予了优先级，高优先级的元素在队列中排在低优先级元素的前面。
以下是 PriorityQueue 的一些重要特性和用法：
-
基本特性：
PriorityQueue是一个基于堆（heap）数据结构实现的，通常是一个最小堆（Min Heap），也可以通过传递比较器来创建最大堆（Max Heap）。- 元素根据其优先级自动排序，高优先级的元素在队列前面。
-
元素插入：
- 使用
add()或offer()方法将元素插入队列中。
- 使用
-
元素获取：
- 使用
peek()方法可以获取队列中优先级最高的元素，但不删除它。 - 使用
poll()方法可以获取并移除队列中优先级最高的元素。
- 使用
-
遍历元素：
PriorityQueue并没有提供迭代器来遍历元素，因为它并不保证元素的顺序。
-
自定义优先级：
- 可以通过为构造函数传递自定义的
Comparator对象来定义元素的优先级比较规则。如果不提供比较器，元素必须实现Comparable接口来自然排序。
- 可以通过为构造函数传递自定义的
-
线程安全性：
PriorityQueue不是线程安全的，如果多个线程同时访问一个PriorityQueue实例，需要进行外部同步处理。
-
应用场景：
PriorityQueue常用于一些需要按优先级处理任务的场景，如任务调度器、最短路径算法（如Dijkstra算法）等。
以下是一个示例，演示了如何创建和使用 PriorityQueue：
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// 创建一个最小堆的PriorityQueue
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 插入元素
minHeap.add(5);
minHeap.add(2);
minHeap.add(8);
// 获取并移除最小元素
int smallest = minHeap.poll(); // 结果：2
System.out.println("Smallest element: " + smallest);
// 获取但不移除最小元素
int smallestPeek = minHeap.peek(); // 结果：5
System.out.println("Smallest element (peek): " + smallestPeek);
}
}
使用比较器构造最大堆
PriorityQueue<ListNode> q = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
这里使用<>来指定元素类型，确保a和b能够正确地识别为ListNode类型，从而访问val属性。
需要注意初始容量不能是0，加入的元素也不能是null
// 使用 Lambda 表达式创建最大堆比较器
Comparator maxHeapComparator = (a, b) -> b - a;
PriorityQueue maxHeap = new PriorityQueue<>(maxHeapComparator);
Comparator是一个函数式接口，它只包含一个抽象方法compare(T o1, T o2)，这个方法接受两个参数并返回一个整数，用于比较这两个对象的大小。由于Comparator是函数式接口，因此可以使用 Lambda 表达式来创建它的实例。
在上述代码中，(a, b) -> b.val - a.val 是一个 Lambda 表达式，它实际上是一个匿名函数，等价于以下的 compare 方法：
int compare(ListNode a, ListNode b) {
return b.val - a.val;
}
Lambda 表达式的左侧 (a, b) 是参数列表，右侧 b.val - a.val 是函数体，表示通过比较 b.val 和 a.val 的差值来确定两个对象的顺序。这个差值为正时，表示 b 比 a 大，为负时，表示 a 比 b 大，为零时，表示它们相等。
因此，Lambda 表达式 (a, b) -> b.val - a.val 是创建了一个比较器，用于按照 ListNode 对象的 val 属性从大到小排序。这个比较器可以传递给 PriorityQueue，以确保最大的节点在堆的顶部。Lambda 表达式的简洁性使得它成为创建匿名函数对象的一种便捷方式。
扩容机制
在 PriorityQueue 中，动态扩容是在插入元素时进行的。以下是动态扩容的一般细节：
初始化：创建一个初始容量（默认是11）的数组，并将第一个元素插入其中。
插入元素：当插入一个新元素时，首先将其添加到数组的末尾。然后，它会根据堆的性质，比较新元素和其父节点的值。如果满足堆的性质，操作结束。如果不满足，就将新元素和父节点交换位置，然后继续比较新元素和新的父节点，直到满足堆的性质为止。
数组扩容：如果在插入元素时发现数组已满，就需要进行扩容。扩容通常会创建一个更大的新数组，然后将所有元素从旧数组复制到新数组中。
扩容策略：通常情况下，扩容的策略是将数组的容量翻倍，以减少频繁扩容的次数。这样可以保持在插入大量元素时的高效性能。
需要注意的是，虽然 PriorityQueue 具有动态扩容的机制，但扩容操作的代价相对较高，因为需要复制数组的所有元素。因此，在处理大量数据时，建议初始化 PriorityQueue 时指定一个足够大的初始容量，以减少扩容的次数，提高性能。
