说到，priority_queue优先队列。必须先要了解啥是堆与运算符重载(我在下方有解释)。
否则只知皮毛，极易忘记==寸步难行。
但在开头，还是简单的说下怎么用
首先，你需要调用
#include <queue>
在main函数中，声明格式为：priority_queue<结构类型> 队列名;
priority_queue <int> i; priority_queue <double> d;
常用操作
priority_queue<int> p; p.size(); // 获取长度 p.empty(); // 是否为空 p.push(val); // 插入 p.pop(); // 删除首个元素 p.top(); // 获取头部元素
以下是完整应用：
priority_queue隶属于<queue>
而queue又是容器适配器。
故，priority_queue也是容器适配器
容器适配器 代表这个函数底层，是可插拔的，能用(vector、deque实现)。
但要注意list不能作为底层容器，因为list不支持随机访问 (如operator[]）
简而言之，priority_queue就像汽车，而内部的发动机，有原装的。如果你不满意，也可以换成其他！
priority_queue<int,vector<int>,cmp> pq; vector<int>就是其底层默认的容器，cmp是重载过后的（结构体or类）
初识：
#include <iostream> #include <queue> using namespace std; struct cmp{ bool operator()(int a,int b){ return a<b; // 因为是正常比较，固为最大堆 // return a>b 最小堆 } }; int main(){ priority_queue<int,vector<int>,cmp> pq; pq.push(3); pq.push(2); pq.push(1); while(pq.size()!=0){ cout<<pq.top()<<endl; pq.pop(); } return 0; }
我看了很多博客，大多数博主，重载的符号都是<符号，而不是()，咱们就在这里说一说。
重载 operator< 的优点：
- 简单直观：直接在类中定义比较逻辑，适合类本身需要一个固定的排序规则。
- 通用性：不仅适用于
priority_queue，还适用于其他需要比较的场景，如sort函数。
自定义比较函数对象的优点：
- 灵活性：可以在不修改类定义的情况下，为不同的排序需求提供多种比较逻辑。
- 避免全局污染：比较逻辑封装在函数对象中，不会影响类的全局比较行为。
源码中的关键逻辑
在priority_queue的底层实现中，堆调整（如push或pop）时会调用比较器：
// 伪代码：堆的上浮操作 void _upheap(int i) { while (i > 0) { int parent = (i-1)/2; if (Compare()(heap[parent], heap[i])) { // 调用operator() swap(heap[parent], heap[i]); i = parent; } else break; } }
底层的简单实现：
其实一下代码，就是堆的低配版，只要知道什么是堆排序，就能够轻松解决优先队列。
#include <iostream> #include <vector> template <typename T> class PriorityQueue { private: std::vector<T> heap; // 上浮操作，用于维护堆的性质 void siftUp(int index) { while (index > 0) { int parent = (index - 1) / 2; if (heap[parent] >= heap[index]) { break; } std::swap(heap[parent], heap[index]); index = parent; } } // 下沉操作，用于维护堆的性质 void siftDown(int index) { int size = heap.size(); while (true) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int largest = index; if (leftChild < size && heap[leftChild] > heap[largest]) { largest = leftChild; } if (rightChild < size && heap[rightChild] > heap[largest]) { largest = rightChild; } if (largest == index) { break; } std::swap(heap[index], heap[largest]); index = largest; } } public: // 判断队列是否为空 bool empty() const { return heap.empty(); } // 获取队列的大小 size_t size() const { return heap.size(); } // 获取堆顶元素 T top() const { if (empty()) { throw std::out_of_range("Priority queue is empty"); } return heap[0]; } // 插入元素 void push(const T& value) { heap.push_back(value); siftUp(heap.size() - 1); } // 删除堆顶元素 void pop() { if (empty()) { throw std::out_of_range("Priority queue is empty"); } std::swap(heap[0], heap.back()); heap.pop_back(); siftDown(0); } }; int main() { PriorityQueue<int> pq; pq.push(3); pq.push(1); pq.push(2); std::cout << "Top element: " << pq.top() << std::endl; pq.pop(); std::cout << "Top element after pop: " << pq.top() << std::endl; return 0; }
大纲
一、前 K 个高频元素-（解析）-结合unordered_map复合运用，了解map的最小单位pair
二、滑动窗口最大值-（解析）-pair<int,int>复合运用，滑动窗口实践
( •̀ ω •́ )✧点击这里，继续学习其他模块吧！
题目：
一、前 K 个高频元素
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
class Solution { struct cmp{ bool operator()(pair<int,int> p1, pair<int,int> p2){ return p1.second<p2.second; // 正常比较 } }; public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> umap; for(int i : nums){ umap[i]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq; for(auto it = umap.begin(); it!=umap.end(); ++it){ pq.push(*it); } vector<int> vec; while(k--){ vec.push_back(pq.top().first); pq.pop(); } return vec; } };
二、滑动窗口最大值
给你一个整数数组
nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
class Solution { struct cmp{ bool operator()(const pair<int,int>& p1,const pair<int,int>& p2){ return p1.first<p2.first; } }; public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> vec; priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> p; for(int i=0; i<k; ++i){ p.push({nums[i],i}); } // 添加第一个滑动窗口的最大值 vec.push_back(p.top().first); for(int i=k; i<nums.size(); ++i){ p.push({nums[i],i}); while(p.top().second<=i-k) p.pop(); vec.push_back(p.top().first); } return vec; } };
三、 游戏 蓝桥真题
问题描述
熊大和熊二在玩游戏。他们将 nn 个正整数 a1,a2,...,ana1,a2,...,an 排成一行，然后各用一个长度为 kk 的框在这个数组中各自随机框选出一段长度为 kk 的连续子序列（随机框选指在合法的 n−k+1n−k+1 个连续子序列中均匀随机）。熊大记录了他框出的 kk 个数中的最大值 PP，熊二记录了他框出的 kk 个数的最小值 QQ，他们突然有个疑问：P−QP−Q 的期望是多少？
2024-11-27 Update：Java 时限调整至 1s
输入描述
输入共 22 行。
第一行为两个正整数 n,kn,k。
第二行为 nn 个由空格隔开的正整数 a1,a2,...,ana1,a2,...,an。
输出描述
输出共 11 行，一个浮点数（请保留两位小数）。
样例输入
3 2 1 2 3
样例输出
1.00
样例说明
一共有四种情况：
熊大框出 [1,2][1,2]，P=2P=2；熊二框出 [1,2][1,2]，Q=1Q=1，P−Q=1P−Q=1。
熊大框出 [1,2][1,2]，P=2P=2；熊二框出 [2,3][2,3]，Q=2Q=2，P−Q=0P−Q=0。
熊大框出 [2,3][2,3]，P=3P=3；熊二框出 [1,2][1,2]，Q=1Q=1，P−Q=2P−Q=2。
熊大框出 [2,3][2,3]，P=3P=3；熊二框出 [2,3][2,3]，Q=2Q=2，P−Q=1P−Q=1。
所以 P−QP−Q 的期望为(1+0+2+1)/4=1.00(1+0+2+1)/4=1.00。
评测用例规模
对于 20%20% 的数据，保证 n≤102n≤102。
对于 40%40% 的数据，保证 n≤103n≤103。
对于 100%100% 的数据，保证 n≤105n≤105，0<ai≤1090<ai≤109，0<k≤n0<k≤n。
#include <iostream> #include <queue> #define ll long long using namespace std; struct max_cmp{ bool operator()(const pair<ll,int>& p1,const pair<ll,int>& p2){ // 最大堆 return p1.first<p2.first; } }; struct min_cmp{ bool operator()(const pair<ll,int>& p1,const pair<ll,int>& p2){ // 最小堆 return p1.first>p2.first; } }; int main() { priority_queue<pair<ll,int>,vector<pair<ll,int>>,max_cmp> max_p; priority_queue<pair<ll,int>,vector<pair<ll,int>>,min_cmp> min_p; int n,k; cin>>n>>k; for(int i=0; i<k; ++i){ // 拓展 ll cur; cin>>cur; max_p.push({cur,i}); min_p.push({cur,i}); } int P,Q; P = max_p.top().first; Q = min_p.top().first; ll sum = P-Q; for(int i=k; i<n; ++i){ // 增加 while(!max_p.empty()&&max_p.top().second<=i-k) max_p.pop(); while(!min_p.empty()&&min_p.top().second<=i-k) min_p.pop(); ll cur; cin>>cur; max_p.push({cur,i}); min_p.push({cur,i}); P = max_p.top().first; Q = min_p.top().first; sum += P-Q; } printf("%.2lf",(double)sum/(n-k+1)); return 0; }
知识点：
重载函数与重载运算符 :: 基础巩固 ::
这里我着重要掌握的是，重载运算符
重载函数
在同一作用域中，可以声明几个功能类似的同名函数。但是形式参数（指参数类型、顺序等）必须不同。如下：
#include <iostream> using namespace std;\ struct printData{ public: void print(int i){ cout<<i<<endl; } void print(double i){ cout<<i<<endl; } void print(char c[]){ cout<<c<<endl; } }; int main(){ printData pd; pd.print(3); return 0; }
重载运算符
语法格式：
class 类名 { public: 返回类型 operator 运算符 (参数列表) { // 运算符的具体运算过程 } }
普通成员函数，以标识符作为函数名。
而重载函数，以 "operator 函数名" 作为函数名。其中operator 表示这是一个重载的运算符。
而后的运算符，就是我们要定义的符号。
如：
a+b; 实际等同于 a.operator + (b)
实例操作：
class Box { private: double length; // 长度 double breadth; // 宽度 double height; // 高度 // 重载 + 运算符，用于把两个 Box 对象相加 Box operator+(const Box& b) { Box box; box.length = this->length + b.length; box.breadth = this->breadth + b.breadth; box.height = this->height + b.height; return box; } }; Box3 = Box1 + Box2;
为啥用 this 时，有->:
在 C++ 中，每一个非静态成员函数都有一个隐含的指针形参，即this指针。
this指针指向调用该成员函数的对象，它是一个常量指针，其类型为类名* const 。
期望 :: 数学知识 ::
期望的由来赌硬币
基础忘记时，可以看看堵硬币
编辑
借鉴博客：
( •̀ ω •́ )✧点击这里，继续学习其他模块吧！
