算法思想之优先级队列

欢迎拜访：雾里看山-CSDN博客
本篇主题：算法思想之优先级队列
发布时间：2025.7.25
隶属专栏：算法

目录

• 算法介绍
• • 队列的基本概念与特性
  • 应用场景与注意事项
• 例题
• • 最后一块石头的重量
  • • 题目链接
    • 题目描述
    • 算法思路
    • 代码实现
  • 数据流中的第 K 大元素
  • • 题目链接
    • 题目描述
    • 算法思路
    • 代码实现
  • 前K个高频单词
  • • 题目链接
    • 题目描述
    • 算法思路
    • 代码实现
  • 数据流的中位数
  • • 题目链接
    • 题目描述
    • 算法思路
    • 代码实现

算法介绍

优先级队列（Priority Queue）是一种特殊的队列结构，其核心思想是 每次出队的元素都是当前队列中优先级最高的元素，而非普通队列的 “先进先出（FIFO）”。这种特性使其在需要动态处理 “优先级导向” 任务的场景中（如任务调度、最短路径求解等）至关重要。

队列的基本概念与特性

定义：优先级队列是一种抽象数据类型（ADT），它支持两种核心操作：

• 插入（Insert）：向队列中添加一个元素，并指定其优先级；
• 提取最高优先级元素（Extract-Max/Extract-Min）：移除并返回队列中优先级最高（或最低）的元素。

此外，通常还支持查看最高优先级元素（Peek） 和修改元素优先级（Decrease-Key/Increase-Key ） 等操作。

关键特性：

• 优先级可以是数值（如整数，数值越大优先级越高）、字符（如 ‘A’ 代表最高优先级）或自定义比较规则；
• 若多个元素优先级相同，通常按插入顺序（FIFO）处理。

应用场景与注意事项

典型应用：

• 任务调度
  • 操作系统的进程调度：高优先级进程（如实时任务）优先占用 CPU；
  • 打印机队列：紧急文档（高优先级）优先打印。
• 最短路径算法（Dijkstra 算法）
  • 在有权图中求解从起点到其他节点的最短路径时，用优先级队列（最小堆）存储 “当前已知最短路径长度”，每次提取路径最短的节点进行扩展，提高算法效率（时间复杂度从 O (n²) 优化为 O (m log n)，n 为节点数，m 为边数）。
• 最大 / 最小 K 问题
  • 求解 “Top K 最大元素”：用大小为 K 的最小堆，遍历元素时若堆未满则插入，否则若元素大于堆顶则替换堆顶并调整，最终堆中元素即为 Top K（时间复杂度 O (n log K)）；
  • 同理可求解 “Bottom K 最小元素”（用最大堆）。
• 哈夫曼编码（Huffman Coding）
  • 数据压缩算法中，用优先级队列（最小堆）存储字符的频率，每次提取频率最小的两个节点合并为新节点，重复此过程构建哈夫曼树，实现高效编码。
• 事件驱动模拟
  • 如离散事件模拟（如银行排队模拟），用优先级队列存储事件（按事件发生时间排序），每次提取最早发生的事件进行处理。

注意事项与优化：

• 选择合适的堆类型：最大堆适用于 “高优先级先出”，最小堆适用于 “低优先级先出”（如最短路径）；
• 自定义优先级规则：在 C++ 中可通过priority_queue的第三个模板参数（比较器）定义优先级（如greater实现最小堆）；
• 避免重复元素：若需去重，插入前需检查元素是否已在队列中（可结合哈希表实现）；
• 大规模数据优化：对于超大规模数据（如分布式场景），可使用分布式优先级队列（如基于 Redis 的 Sorted Set）。

例题

最后一块石头的重量

题目链接

1046. 最后一块石头的重量

题目描述

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0 。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

算法思路

其实就是一个模拟的过程：

• 每次从石堆中拿出最大的元素以及次大的元素，然后将它们粉碎；
• 如果还有剩余，就将剩余的⽯头继续放在原始的石堆里面

重复上面的操作，直到石堆里面只剩下一个元素，或者没有元素（因为所有的石头可能全部抵消了）

具体的实现逻辑：

• 我们可以创建一个大根堆；
• 然后将所有的石头放入大根堆中；
• 每次拿出前两个堆顶元素粉碎一下，如果还有剩余，就将剩余的石头继续放入堆中；

代码实现

class Solution {public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> pq(stones.begin(), stones.end()); while(pq.size()>1) { int first = pq.top(); pq.pop(); int second = pq.top(); pq.pop(); if(first>second) pq.push(first-second); } if(pq.empty()) return 0; return pq.top(); }};

数据流中的第 K 大元素

题目链接

703. 数据流中的第 K 大元素

题目描述

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例 1：

输入：
[“KthLargest”, “add”, “add”, “add”, “add”, “add”]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8

示例 2：

输入：
[“KthLargest”, “add”, “add”, “add”, “add”]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
输出：[null, 7, 7, 7, 8]
解释：
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // 返回 7
kthLargest.add(10); // 返回 7
kthLargest.add(9); // 返回 7
kthLargest.add(9); // 返回 8

提示：

• 0 <= nums.length <= 104
• 1 <= k <= nums.length + 1
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• 最多调用 add 方法 104 次

算法思路

从标题可以看出，这是一个TopK的问题，我们只需要建一个大小为k的小根堆即可

代码实现

class KthLargest {private: priority_queue<int, vector<int>, greater<int>> pq; int _k;public: KthLargest(int k, vector<int>& nums) { _k = k; for(auto& num : nums) { pq.push(num); if(pq.size() > _k) pq.pop(); } } int add(int val) { pq.push(val); if(pq.size() > _k) pq.pop(); return pq.top(); }};

前K个高频单词

题目链接

692. 前K个高频单词

题目描述

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例 1：

输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

注意：

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] 由小写英文字母组成。
• k 的取值范围是 [1, 不同 words[i] 的数量]

算法思路

先进行单词统计：
我们需要知道每一个单词出现的频次，因此可以先使用哈希表，统计出每一个单词出现的频次；
然后在哈希表中，选出前 k 大的单词

处理TopK问题：
先定义一个自定义排序，我们需要的是前 k 大，因此需要一个小根堆。但是当两个字符串的频次相同的时候，我们需要的是字典序较小的，此时是一个大根堆的属性，在定义比较器的时候需要注意！

• 当两个字符串出现的频次不同的时候：需要的是基于频次比较的小根堆
• 当两个字符串出现的频次相同的时候：需要的是基于字典序比较的大根堆

定义好比较器之后，依次将哈希表中的字符串插入到堆中，维持堆中的元素不超过 k 个；
遍历完整个哈希表后，堆中的剩余元素就是前 k ⼤的元素；

代码实现

class Solution { typedef pair<string, int> psi; struct cmp { bool operator()(const psi& a, const psi& b) { if(a.second == b.second) return a.first < b.first; return a.second > b.second; } };public: vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string,int> hash; for(string word : words) hash[word]++; priority_queue<psi , vector<psi>, cmp> heap; for(auto& psi : hash) { heap.push(psi); if(heap.size() > k) heap.pop(); } vector<string> ret(k); for(int i = k-1; i >= 0; --i) { ret[i] = heap.top().first; heap.pop(); } return ret; }};

数据流的中位数

题目链接

295. 数据流的中位数

题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。
  示例 1：

输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

• -105 <= num <= 105
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 104 次调用 addNum 和 findMedian

算法思路

我们可以将整个数组「按照大小」平分成两部分（如果不能平分，那就让较大部分的元素多⼀个），
较大的部分称为左侧部分，较小的部分称为右侧部分：

• 将左侧部分放入 大根堆中，然后将右侧元素放入 小根堆 中；
• 这样就能在 O(1) 的时间内拿到中间的一个数或者两个数，进而求的平均数。

代码实现

class MedianFinder { priority_queue<int> max_heap; priority_queue<int, vector<int>, greater<int>> min_heap;public: MedianFinder() { } void addNum(int num) { if(max_heap.size() == min_heap.size()) { min_heap.push(num); int cur = min_heap.top(); min_heap.pop(); max_heap.push(cur); } else { max_heap.push(num); int cur = max_heap.top(); max_heap.pop(); min_heap.push(cur); } } double findMedian() { if(min_heap.size() == max_heap.size()) return (min_heap.top()+max_heap.top())/2.0; return max_heap.top(); }};

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！

法制资讯发布平台