C++ 优先级队列(大小根堆)OJ

本文主要是介绍C++ 优先级队列(大小根堆)OJ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1、 1046. 最后一块石头的重量

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

        为什么小根堆可以解决TopK问题？ 

3、 692. 前K个高频单词

4、 295. 数据流的中位数

---

1、 1046. 最后一块石头的重量

 思路：根据示例发现可以用大根堆(降序)模拟这个过程。

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for (auto s : stones)heap.push(s);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;}
};

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

 思路：TopK问题使用小根堆堆解决，priority_queue（默认大根堆）的第三个参数为greater<类型>即为小根堆。

class KthLargest {
public:int _k;priority_queue<int, vector<int>, greater<int>> heap;KthLargest(int k, vector<int>& nums) {_k = k;for (auto n : nums) {heap.push(n);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);*/

为什么小根堆可以解决TopK问题？ 

对于设计一个找到数据流中第k大元素的类的问题，我们应该使用小根堆（Min Heap）来实现。下面解释为什么使用小根堆以及如何使用它：

1. 为什么使用小根堆:

   • 小根堆能够保证堆顶元素是堆中最小的元素。在维护数据流中的第k大元素时，我们希望能够快速访问到第k大的元素，而不是最小的元素。通过维护一个大小为k的小根堆，堆中的元素就是数据流中最大的k个元素，而堆顶元素（最小元素）就是这k个元素中第k大的元素。
   • 当新的元素加入时，如果它大于堆顶元素，我们就将它加入堆中，并移除堆顶元素，这样堆的大小仍然保持为k。这样做可以确保堆中始终是数据流中最大的k个元素，而堆顶元素就是这些元素中最小的，即第k大的元素。

2. 如何使用小根堆:

   • 初始化时，将数组nums中的元素加入小根堆中，如果元素数量超过k，则移除堆顶元素，以保证堆的大小为k。
   • 对于add方法，每次加入一个新元素时，先将其加入到小根堆中。如果加入后堆的大小超过k，则移除堆顶元素。然后返回堆顶元素，即为当前数据流中第k大的元素。

通过使用小根堆，我们可以高效地解决数据流中的第k大元素问题，同时保证时间复杂度和空间复杂度都在合理的范围内。

3、 692. 前K个高频单词

 思路：

• 频次统计：首先，使用哈希表记录每个单词出现的频次。
• 优先队列排序：利用优先队列（或小根堆）根据单词的频次和字典序排序，从而找出频次最高的前 k 个单词。

实现步骤

1. 处理单词列表：

   • 利用哈希表统计每个单词出现的次数，确保单词不会重复计数且记录了它们的频次。

2. 使用小根堆选择前 k 大元素：

   • 根据问题要求，设计比较器（cmp）：
     • 频次不同：频次较少的优先（小根堆性质）。
     • 频次相同：字典序较小的优先（大根堆性质）。
   • 使用优先队列（小根堆）存储单词及其频次，保证堆的大小不超过 k。
   • 将每个单词和它的频次插入到堆中，如果堆的大小超过了 k，就移除堆顶元素。

3. 获取结果：

   • 最终，堆中剩余的就是频次最高的前 k 个单词。反向遍历堆，将元素按正确的顺序存入结果列表中。

class Solution {
public: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;}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> hash;for(auto& s:words)hash[s]++;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;}
};

4、 295. 数据流的中位数

实现一个动态中位数查找器

 动态数据流中位数查找是一种常见问题，可以通过聪明地运用数据结构来解决。以下是如何通过维护两个堆：一个大根堆和一个小根堆—来实现一个动态中位数查找器的步骤。

解决方法：利用两个堆

算法思路

本解法是一个关于堆数据结构的经典应用。通过将数据流平分或近似平分为两个部分：一个较小部分和一个较大部分—可以高效解决问题：

• 较小的部分在大根堆（left）中。

• 较大的部分在小根堆（right）中。

• 如此设置允许我们在常数时间内获得中位数。

动态添加数据

我们需要保证left比right大1或者left等于right，这样才能算出中位数，当有新数据加入时，进行以下步骤以保持两个堆的平衡：

1. 两个堆的大小相同 (left.size() == right.size()):

   • 若堆为空，直接将 num 放入 left 中。

   • 若 num <= left.top()，将 x 放入 left。

   • 否则，先将 num 放入 right，再将 right 的堆顶元素移到 left 中。

2. 两个堆的大小不相同 (left.size() > right.size()+1):

   • 若 num 小于或等于 left.top()，再将 left 的堆顶元素移到 right 中。

   • 否则，将 num 放入 right，

查找中位数

• 若两个堆的大小相同，中位数是两个堆顶元素的平均值。

• 否则，中位数是 left 堆的顶元素。

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();}
};

这篇关于C++ 优先级队列(大小根堆)OJ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---