本文主要是介绍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.使用示例
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 个元素。
代码示例:
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 个链表的头节点加入堆中。
反复从堆中弹出最小的元素,并将下一个节点加入堆中,直到堆为空。
代码示例:
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 时移除堆顶元素。
代码示例
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 个单位时间。
解题思路:
使用最大堆来存储任务,根据任务的剩余次数排序。
每次从堆中取出任务执行并将其放入等待队列,直到冷却时间结束后再重新加入堆中。
代码示例
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(数据流的中位数)
题目描述: 不断从数据流中读取整数并计算当前所有整数的中位数。
解题思路:
使用两个堆:一个最大堆存储数据流中较小的一半,另一个最小堆存储较大的一半。这样最大堆堆顶元素就是中位数。
每次插入新的数据时,根据其大小放入相应的堆中,并保持两个堆的平衡。
代码示例
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;}}
}
优先队列是一种强大的数据结构,能够高效地解决一系列问题,特别是在处理需要动态获取最值或维持一定顺序的场景时。通过以上例题,可以看到优先队列在不同场景下的广泛应用。
这篇关于Java中优先队列API的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!