Leetcode 优先队列详解

优先队列

优先队列（Priority Queue）：一种特殊的队列。在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先删除

普通队列详解Leetcode 队列详解

优先队列与普通队列最大的不同点在于出队顺序

• 普通队列的出队顺序跟入队顺序相关，符合「先进先出（First in, First out）」的规则。
• 优先队列的出队顺序跟入队顺序无关，优先队列是按照元素的优先级来决定出队顺序的。优先级高的元素优先出队，优先级低的元素后出队。优先队列符合 「最高级先出（First in, Largest out）」 的规则

适用场景

优先队列的应用场景非常多，比如：

• 数据压缩：赫夫曼编码算法
• 最短路径算法：Dijkstra 算法
• 最小生成树算法：Prim 算法
• 任务调度器：根据优先级执行系统任务
• 事件驱动仿真：顾客排队算法
• 排序问题：查找第 k 个最小元素

很多语言都提供了优先级队列的实现。比如，Java 的PriorityQueue，C++ 的priority_queue

Leetcode 真题

数组中的第K个最大元素

解题思路： 典型的优先队列/最大堆，依次入队排序后取队头的第K大的元素

public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});for (int num : nums) {if (queue.size() == k) {if (queue.peek() < num) {queue.poll();queue.offer(num);}} else {queue.offer(num);}}return queue.poll();
}

前 K 个高频元素

解题思路：使用优先队列记录出现次数topK
int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数

public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();for (int num : nums) {occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] m, int[] n) {return m[1] < n[1] ? -1 : 1;}});for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {if (queue.peek()[1] < count) {queue.poll();queue.offer(new int[]{num, count});}} else {queue.offer(new int[]{num, count});}}int[] ret = new int[k];for (int i = 0; i < k; ++i) {ret[k - i - 1] = queue.poll()[0];}return ret;
}

滑动窗口最大值

解题思路：使用优先队列记录窗口范围内的topK大数
int[] 的第一个元素代表数组的值，第二个元素代表了该值的下标
根据数组元素从大到小进行排序，若是元素相同的话，则根据下标进行从大到小进行排序

public int[] maxSlidingWindow(int[] nums, int k) {int[] result = new int[nums.length - k + 1];PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0];}});for (int i = 0; i < k - 1; i++) {queue.offer(new int[]{nums[i], i});}for (int i = k - 1; i < nums.length; i++) {queue.offer(new int[]{nums[i], i});// 若是优先队列/最大堆的堆顶元素 不在滑动窗口范围内，则直接从优先队列中进行删除while(queue.peek()[1] <= i - k){queue.poll();}result[i - k + 1] = queue.peek()[0];}return result;
}

---

参考资料：

1. 优先队列知识
2. Leetcode 队列详解