优先队列（典型算法思想）——OJ例题算法解析思路

目录

一、1046. 最后一块石头的重量 - 力扣（LeetCode）

算法代码： 

代码思路

使用优先队列（大根堆）

将所有石头放入堆中

模拟碰撞过程

返回最后的重量

代码解析

时间复杂度

示例

输入

输出

二、703. 数据流中的第 K 大元素 - 力扣（LeetCode） 

算法代码： 

代码思路

使用小根堆（最小堆）

构造函数

添加元素的方法

代码解析

时间复杂度

示例

输入

输出

三、692. 前K个高频单词 - 力扣（LeetCode）

算法代码： 

代码思路

统计单词频率

自定义比较器

维护小根堆

提取结果

代码解析

时间复杂度

示例

输入

输出

四、295. 数据流的中位数 - 力扣（LeetCode） 

算法代码： 

代码思路

使用两个堆

添加数字

计算中位数

代码解析

时间复杂度

示例

使用示例

输出

---

一、1046. 最后一块石头的重量 - 力扣（LeetCode）

算法代码：  class Solution { public: int lastStoneWeight(vector<int>& stones) { // 1. 创建⼀个⼤根堆 priority_queue<int> heap; // 2. 将所有元素丢进这个堆⾥⾯ for (auto x : stones) heap.push(x); // 3. 模拟这个过程 while (heap.size() > 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); if (a > b) heap.push(a - b); } return heap.size() ? heap.top() : 0; } }; 代码思路 使用优先队列（大根堆）

利用 priority_queue 来模拟石头的碰撞过程。大根堆可以帮助我们快速找到当前最重的两块石头。

将所有石头放入堆中

通过循环将给定的石头重量插入到优先队列中。这样，最重的石头将始终位于堆的顶部。

模拟碰撞过程

使用 while 循环，当堆中石头的数量大于 1 时，继续进行碰撞。

从堆中取出两块最重的石头（a 和 b）。

如果 a 和 b 不相等，将它们的重量差（a - b）重新放回堆中。

如果它们相等，则两块石头都被摧毁，不会被放回堆中。

返回最后的重量

当堆中只剩下一个石头时，返回这个石头的重量；如果没有石头剩下，则返回 0。

代码解析 class Solution { public: int lastStoneWeight(vector<int>& stones) { // 1. 创建一个大根堆 priority_queue<int> heap; // 2. 将所有元素丢进这个堆里面 for (auto x : stones) heap.push(x); // 3. 模拟这个过程 while (heap.size() > 1) { int a = heap.top(); // 取出最大元素 heap.pop(); // 移除最大元素 int b = heap.top(); // 取出第二大元素 heap.pop(); // 移除第二大元素 if (a > b) // 如果不相等，进队差值 heap.push(a - b); } return heap.size() ? heap.top() : 0; // 返回最后的重量 } }; 时间复杂度

将所有石头插入到优先队列的时间复杂度是 O(n log n)，其中 n 是石头的数量。

每次从堆中取出两个元素并可能插入一个元素的操作时间复杂度是 O(log n)，这在最坏情况下会进行 n 次，因此整体最坏的时间复杂度为 O(n log n)。

示例 输入 vector<int> stones = {2, 7, 4, 1, 8, 1}; Solution sol; cout << sol.lastStoneWeight(stones); // 输出：1 输出

在这个例子中，最终剩下的石头重量是 1。

这种方法通过使用大根堆有效地处理了石头碰撞的问题，能够快速找到最重的石头并进行处理。

二、703. 数据流中的第 K 大元素 - 力扣（LeetCode） 

算法代码：  class KthLargest { // 创建⼀个⼤⼩为 k 的⼩跟堆 priority_queue<int, vector<int>, greater<int>> heap; int _k; public: KthLargest(int k, vector<int>& nums) { _k = k; for (auto x : nums) { heap.push(x); if (heap.size() > _k) heap.pop(); } } int add(int val) { heap.push(val); if (heap.size() > _k) heap.pop(); return heap.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */ 代码思路

使用小根堆（最小堆）

利用 priority_queue 来创建一个小根堆，堆中最多保留 k 个元素。小根堆的特性是堆顶（即顶部元素）是当前堆中最小的元素。

构造函数

KthLargest(int k, vector<int>& nums) 构造函数接受一个整数 k 和一个整数数组 nums。

将数组中的元素依次插入到小根堆中，对于每个插入的元素，如果堆的大小超过 k，则移除堆顶元素（即最小元素）。

这样在堆中始终保持 k 个最大的元素，堆顶元素即为第 k 大的元素。

添加元素的方法

int add(int val) 方法用于向数据结构中添加一个新元素 val。

将新元素插入堆中，并再次检查堆的大小。如果堆的大小超过 k，则移除堆顶元素。

返回当前堆顶元素，这个元素就是当前的第 k 大元素。

代码解析 class KthLargest { // 创建一个大小为 k 的小根堆 priority_queue<int, vector<int>, greater<int>> heap; int _k; public: KthLargest(int k, vector<int>& nums) { _k = k; // 初始化 k for (auto x : nums) { heap.push(x); // 将元素插入堆中 if (heap.size() > _k) // 如果堆的大小超过 k heap.pop(); // 移除堆顶元素 } } int add(int val) { heap.push(val); // 插入新元素 if (heap.size() > _k) // 如果堆的大小超过 k heap.pop(); // 移除堆顶元素 return heap.top(); // 返回当前的第 k 大元素 } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */ 时间复杂度

在构造函数中，插入 n 个元素到堆中的时间复杂度为 O(n log k)，因为每次插入堆的操作是 O(log k)。

在 add 方法中，每次插入和检索操作的时间复杂度为 O(log k)。

整个算法的空间复杂度为 O(k)，因为堆中最多存储 k 个元素。

示例 输入 int k = 3; vector<int> nums = {4, 5, 8, 2}; KthLargest* obj = new KthLargest(k, nums); int param_1 = obj->add(3); // 返回 4 int param_2 = obj->add(5); // 返回 5 int param_3 = obj->add(10); // 返回 5 int param_4 = obj->add(9); // 返回 8 int param_5 = obj->add(4); // 返回 8 输出

param_1 为 4，说明现在的第 3 大元素是 4。

param_2 为 5，说明现在的第 3 大元素是 5。

param_3 为 5，依然是第 3 大元素。

param_4 为 8，说明现在的第 3 大元素是 8。

param_5 也为 8，依然是第 3 大元素。

这种实现方式通过小根堆高效地维护了动态数组中第 k 大元素的状态，适合于需要频繁添加元素并查询第 k 大元素的场景。

 

三、692. 前K个高频单词 - 力扣（LeetCode）

算法代码：  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) { // 1. 统计⼀下每⼀个单词的频次 unordered_map<string, int> hash; for (auto& s : words) hash[s]++; // 2. 创建⼀个⼤⼩为 k 的堆 priority_queue<PSI, vector<PSI>, cmp> heap; // 3. TopK 的主逻辑 for (auto& psi : hash) { heap.push(psi); if (heap.size() > k) heap.pop(); } // 4. 提取结果 vector<string> ret(k); for (int i = k - 1; i >= 0; i--) { ret[i] = heap.top().first; heap.pop(); } return ret; } }; 代码思路

统计单词频率

使用 unordered_map<string, int> 来统计每个单词在输入数组中的出现次数。

自定义比较器

定义一个结构体 cmp，用于优先队列中元素的比较。这个比较器实现了以下逻辑：

如果两个单词的频率相同，则按字典序进行排序（按字母逆序，即较大的字母排在前面，形成一个大根堆）。

否则，频率较高的单词应排在前面（形成一个小根堆）。

维护小根堆

使用 priority_queue 来创建一个小根堆，存储单词及其频率。

遍历频率统计的哈希表，将每个单词及其频率插入堆中。如果堆的大小超过 k，则弹出堆顶元素，从而保持堆中只包含 k 个频率最高的单词。

提取结果

创建一个结果向量 ret，用于存储最终的 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) { // 1. 统计每一个单词的频次 unordered_map<string, int> hash; for (auto& s : words) hash[s]++; // 2. 创建一个大小为 k 的小根堆 priority_queue<PSI, vector<PSI>, cmp> heap; // 3. TopK 的主逻辑 for (auto& psi : hash) { heap.push(psi); // 插入单词频率对 if (heap.size() > k) // 如果堆的大小超过 k heap.pop(); // 移除堆顶元素 } // 4. 提取结果 vector<string> ret(k); // 结果向量 for (int i = k - 1; i >= 0; i--) { ret[i] = heap.top().first; // 获取堆顶元素的单词 heap.pop(); // 移除堆顶元素 } return ret; // 返回结果 } }; 时间复杂度

统计频率的时间复杂度为 O(n)，其中 n 是单词数组的长度。

在最坏情况下，当哈希表中有 n 个不同单词时，维护小根堆的时间复杂度为 O(n log k)，因为每次插入和删除堆顶的操作都是 O(log k)。

因此，整体时间复杂度为 O(n log k)。

示例 输入 vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"}; int k = 2; Solution sol; vector<string> result = sol.topKFrequent(words, k); // 返回 {"i", "love"} 输出

result 包含了出现频率最高的两个单词 “i” 和 "love"。

这种实现方式通过使用哈希表和小根堆有效地解决了查找第 k 个频繁单词的问题，能够快速处理数据并返回结果。

四、295. 数据流的中位数 - 力扣（LeetCode） 

算法代码：  class MedianFinder { priority_queue<int> left; // ⼤根堆 priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆 public: MedianFinder() {} void addNum(int num) { // 分类讨论即可 if (left.size() == right.size()) // 左右两个堆的元素个数相同 { if (left.empty() || num <= left.top()) // 放 left ⾥⾯ { left.push(num); } else { right.push(num); left.push(right.top()); right.pop(); } } else { if (num <= left.top()) { left.push(num); right.push(left.top()); left.pop(); } else { right.push(num); } } } double findMedian() { if (left.size() == right.size()) return (left.top() + right.top()) / 2.0; else return left.top(); } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */ 代码思路

使用两个堆

大根堆 (left)：存储较小的一半数字，堆顶是这部分数字的最大值。

小根堆 (right)：存储较大的一半数字，堆顶是这部分数字的最小值。

添加数字

当添加一个新的数字时，根据当前两个堆的大小和新数字的值决定将其放入哪个堆：

如果两个堆的大小相同，且新数字小于等于大根堆的堆顶，则将其放入大根堆；否则，将其放入小根堆，然后将小根堆的堆顶元素移到大根堆中。

如果大根堆的大小大于小根堆，且新数字小于等于大根堆的堆顶，则将其放入大根堆，并将其堆顶元素移到小根堆；否则，直接放入小根堆。

这样可以保证大根堆的元素总是小于等于小根堆的元素，并且大根堆的大小要么等于小根堆的大小，要么大一个元素。

计算中位数

如果两个堆的大小相等，则中位数为两个堆顶元素的平均值。

如果大根堆的大小大于小根堆，则中位数为大根堆的堆顶元素。

 

代码解析 class MedianFinder { priority_queue<int> left; // 大根堆 priority_queue<int, vector<int>, greater<int>> right; // 小根堆 public: MedianFinder() {} void addNum(int num) { // 分类讨论 if (left.size() == right.size()) // 左右两个堆的元素个数相同 { if (left.empty() || num <= left.top()) // 放入大根堆 { left.push(num); } else { // 放入小根堆 right.push(num); left.push(right.top()); right.pop(); } } else { // 大根堆的元素个数大于小根堆 if (num <= left.top()) { left.push(num); right.push(left.top()); left.pop(); } else { right.push(num); } } } double findMedian() { if (left.size() == right.size()) return (left.top() + right.top()) / 2.0; // 两堆大小相同 else return left.top(); // 大根堆较多 } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */ 时间复杂度

addNum 方法的时间复杂度是 O(log n)，因为每次插入堆的时间复杂度为 O(log n)。

findMedian 方法的时间复杂度是 O(1)，因为只需返回堆顶元素。

整体的空间复杂度是 O(n)，存储所有的数字。

示例 使用示例 MedianFinder* obj = new MedianFinder(); obj->addNum(1); obj->addNum(2); double median1 = obj->findMedian(); // 返回 1.5 obj->addNum(3); double median2 = obj->findMedian(); // 返回 2.0 输出

第一次调用 findMedian() 时，返回 1.5，因为当前的数字是 1 和 2。

第二次调用时，返回 2.0，因为当前的数字是 1、2 和 3。

这种实现方式通过使用两个堆来高效地维护动态数据集的中位数，适用于需要频繁添加数字并查询中位数的场景。