Java中优先队列API

Java中的优先队列（PriorityQueue）是一个基于堆实现的无界队列，优先队列中的元素按照自然顺序或者通过提供的比较器排序。

1. 构造方法

PriorityQueue(): 创建一个默认初始容量为11的空优先队列，并根据其元素的自然顺序对其进行排序。

PriorityQueue(int initialCapacity): 创建一个指定初始容量的空优先队列，并根据其元素的自然顺序对其进行排序。

PriorityQueue(int initialCapacity, Comparator<? super E> comparator): 创建一个指定初始容量的空优先队列，并使用给定的比较器对元素进行排序。

PriorityQueue(Collection<? extends E> c): 创建一个优先队列，并根据提供的集合 c 的元素自然顺序对其进行排序。

PriorityQueue(PriorityQueue<? extends E> c): 创建一个优先队列，包含与给定优先队列相同的元素。

PriorityQueue(SortedSet<? extends E> c): 创建一个优先队列，包含与给定有序集合相同的元素。

2.常用方法

插入与删除操作
boolean add(E e): 将指定的元素插入到优先队列中。如果插入成功，返回 true。

boolean offer(E e): 与 add(E e) 类似，都是将元素插入到优先队列中。这个方法在元素无法插入时返回 false。

E poll(): 获取并移除队列的头元素，如果队列为空，则返回 null。

E remove(): 获取并移除队列的头元素，如果队列为空，则抛出 NoSuchElementException。

访问操作
E peek(): 获取但不移除队列的头元素，如果队列为空，则返回 null。
E element(): 获取但不移除队列的头元素，如果队列为空，则抛出 NoSuchElementException。

批量操作
boolean remove(Object o): 从队列中移除指定的元素，如果存在多个相同的元素，只移除其中一个。如果移除成功返回 true，否则返回 false。
boolean contains(Object o): 检查优先队列是否包含指定的元素，返回 true 或 false。
int size(): 返回优先队列中的元素个数。
boolean isEmpty(): 检查队列是否为空，如果为空返回 true，否则返回 false。
void clear(): 清空优先队列，移除所有元素。

集合操作
Object[] toArray(): 返回包含优先队列中所有元素的数组。
<T> T[] toArray(T[] a): 返回包含优先队列中所有元素的数组，并将其存储在给定的数组 a 中。

迭代操作
Iterator<E> iterator(): 返回队列元素的迭代器，但不能保证顺序。

3.使用示例

java">import java.util.PriorityQueue;
import java.util.Comparator;public class PriorityQueueExample {public static void main(String[] args) {// 创建一个自然顺序的优先队列PriorityQueue<Integer> pq = new PriorityQueue<>();// 添加元素pq.offer(5);pq.offer(1);pq.offer(3);pq.offer(10);// 获取并移除队列的头元素System.out.println("poll: " + pq.poll()); // 输出 1// 获取但不移除队列的头元素System.out.println("peek: " + pq.peek()); // 输出 3// 检查是否包含元素System.out.println("contains 5? " + pq.contains(5)); // 输出 true// 移除元素pq.remove(5);System.out.println("contains 5 after removal? " + pq.contains(5)); // 输出 false// 迭代队列元素System.out.println("Queue elements:");for (int num : pq) {System.out.println(num);}}
}

4.特性与注意事项

排序规则:
PriorityQueue 基于最小堆实现，因此默认情况下，队列的头元素是最小元素（即自然顺序中最小的元素）。
你可以提供一个 Comparator 来定义自定义的排序规则。

性能:
插入元素（add() 和 offer()）的时间复杂度为 O(log n)。
访问或移除队列头元素（peek()、poll()、remove()）的时间复杂度为 O(log n)。

线程安全:
PriorityQueue 不是线程安全的。如果多个线程要并发访问优先队列，则建议使用线程安全的变体 PriorityBlockingQueue。

元素的排序顺序:
如果优先队列中的元素不实现 Comparable 接口，或者你没有提供 Comparator，在尝试插入时会抛出 ClassCastException。

5.常见算法解题

优先队列（PriorityQueue）在很多常见的算法问题中都能派上用场，尤其是那些涉及到排序、动态获取最值或需要高效处理数据的问题。以下是几个常见的算法题目，通常可以使用优先队列来高效解决：

5.1 Top K Frequent Elements（前 K 个高频元素）

题目描述: 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

解题思路:
使用哈希表统计每个元素的出现频率。
使用一个大小为 k 的最小堆来维护出现频率最高的 k 个元素。
代码示例:

java">import java.util.*;public class TopKFrequentElements {public List<Integer> topKFrequent(int[] nums, int k) {Map<Integer, Integer> frequencyMap = new HashMap<>();for (int num : nums) {frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);}PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {minHeap.offer(entry);if (minHeap.size() > k) {minHeap.poll();}}List<Integer> result = new ArrayList<>();while (!minHeap.isEmpty()) {result.add(minHeap.poll().getKey());}Collections.reverse(result);return result;}
}

5.2 Merge K Sorted Lists（合并 K 个排序链表）

题目描述: 合并 k 个排序链表，并将它们合并为一个排序链表。

解题思路:
使用一个最小堆，每次将 k 个链表的头节点加入堆中。
反复从堆中弹出最小的元素，并将下一个节点加入堆中，直到堆为空。
代码示例：

java">import java.util.*;public class MergeKSortedLists {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));for (ListNode list : lists) {if (list != null) {minHeap.offer(list);}}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!minHeap.isEmpty()) {ListNode node = minHeap.poll();current.next = node;current = current.next;if (node.next != null) {minHeap.offer(node.next);}}return dummy.next;}class ListNode {int val;ListNode next;ListNode(int val) { this.val = val; }}
}

5.3 Kth Largest Element in an Array（数组中第 K 大的元素）

题目描述: 给定一个未排序的数组，找到其中第 k 个最大的元素。
解题思路:
维护一个大小为 k 的最小堆，堆顶元素即为当前的第 k 大元素。
遍历数组，将元素加入堆中，并在堆大小超过 k 时移除堆顶元素。
代码示例

java">import java.util.*;public class KthLargestElement {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int num : nums) {minHeap.offer(num);if (minHeap.size() > k) {minHeap.poll();}}return minHeap.peek();}
}

5.4 Task Scheduler（任务调度器）

题目描述: 给定一组任务和一个冷却时间 n，要求设计一种调度算法使得相同任务之间至少相隔 n 个单位时间。

解题思路:
使用最大堆来存储任务，根据任务的剩余次数排序。
每次从堆中取出任务执行并将其放入等待队列，直到冷却时间结束后再重新加入堆中。

代码示例

java">import java.util.*;public class TaskScheduler {public int leastInterval(char[] tasks, int n) {Map<Character, Integer> taskCounts = new HashMap<>();for (char task : tasks) {taskCounts.put(task, taskCounts.getOrDefault(task, 0) + 1);}PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());maxHeap.addAll(taskCounts.values());int cycles = 0;while (!maxHeap.isEmpty()) {List<Integer> tempList = new ArrayList<>();for (int i = 0; i <= n; i++) {if (!maxHeap.isEmpty()) {tempList.add(maxHeap.poll());}}for (int count : tempList) {if (--count > 0) {maxHeap.offer(count);}}cycles += maxHeap.isEmpty() ? tempList.size() : n + 1;}return cycles;}
}

5.5 Find Median from Data Stream（数据流的中位数）

题目描述: 不断从数据流中读取整数并计算当前所有整数的中位数。

解题思路:
使用两个堆：一个最大堆存储数据流中较小的一半，另一个最小堆存储较大的一半。这样最大堆堆顶元素就是中位数。
每次插入新的数据时，根据其大小放入相应的堆中，并保持两个堆的平衡。
代码示例

java">import java.util.*;public class MedianFinder {private PriorityQueue<Integer> lowerHalf;private PriorityQueue<Integer> upperHalf;public MedianFinder() {lowerHalf = new PriorityQueue<>(Collections.reverseOrder());upperHalf = new PriorityQueue<>();}public void addNum(int num) {lowerHalf.offer(num);upperHalf.offer(lowerHalf.poll());if (lowerHalf.size() < upperHalf.size()) {lowerHalf.offer(upperHalf.poll());}}public double findMedian() {if (lowerHalf.size() > upperHalf.size()) {return lowerHalf.peek();} else {return (lowerHalf.peek() + upperHalf.peek()) / 2.0;}}
}