优先队列(priority_queue)

我之前博客中有队列相关的知识点但是不完全其中有简单队列也有单调队列现在我们着重看一下优先队列优先队列一般有两种用法---大根堆和小根堆一般用于求第k大/第k小的数或者贪心类问题priority_queueint qp; //大根堆先出大数 priority_queueint,vectorint,greaterint qp; //小根堆先出小数而优先队列的常用操作与栈相似都归结如下q.push(x); // 插入元素 q.top(); // 获取堆顶元素最大/最小 q.pop(); // 删除堆顶 q.empty(); // 判断空 q.size(); // 元素数量用优先队列时我们要注意当队列为空时不能用top/pop否则程序会崩溃。下面我们看几道比较经典的例题给你一个长度为n的整数数组score其中score[i]是第i位运动员在比赛中的得分。所有得分都互不相同。运动员将根据得分决定名次其中名次第1的运动员得分最高名次第2的运动员得分第2高依此类推。运动员的名次决定了他们的获奖情况名次第1的运动员获金牌Gold Medal。名次第2的运动员获银牌Silver Medal。名次第3的运动员获铜牌Bronze Medal。从名次第4到第n的运动员只能获得他们的名次编号即名次第x的运动员获得编号x。使用长度为n的数组answer返回获奖其中answer[i]是第i位运动员的获奖情况。示例 1输入score [5,4,3,2,1]输出[Gold Medal,Silver Medal,Bronze Medal,4,5]解释名次为 [1st, 2nd, 3rd, 4th, 5th] 。这道题我们可以用优先队列与pair结合用pair存储下标与成绩队列顶部一定为目前最大值代码class Solution { public: vectorstring findRelativeRanks(vectorint score) { int nscore.size(); priority_queuepairint,intq; for(int i0;in;i){ q.emplace(score[i],i); } vectorstring ans(n); int k1; while(!q.empty()){ auto [s,idx]q.top();//大根堆q的最大值存入S,对应下标存入idx; q.pop(); if(k1) ans[idx]Gold Medal; else if(k2) ans[idx]Silver Medal; else if(k3) ans[idx]Bronze Medal; else ans[idx]to_string(k); k; } return ans; } };数据流中的第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); // 返回 4kthLargest.add(5); // 返回 5kthLargest.add(10); // 返回 5kthLargest.add(9); // 返回 8kthLargest.add(4); // 返回 8这道题我们就用小根堆当堆里面有k个元素时堆顶就是第k大元素代码class KthLargest { private: int k; priority_queueint, vectorint, greaterint minHeap; // 小根堆 public: KthLargest(int k, vectorint nums) { this-k k; for (int num : nums) { add(num); // 复用add逻辑初始化堆 } } int add(int val) { if (minHeap.size() k) { minHeap.push(val); } else if (val minHeap.top()) { minHeap.pop(); minHeap.push(val); } return minHeap.top(); // 堆顶就是第k大元素 } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj new KthLargest(k, nums); * int param_1 obj-add(val); */