说到，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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 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 。
期望 :: 数学知识 ::
期望的由来赌硬币
基础忘记时，可以看看堵硬币
借鉴博客：
1、C++ 重载运算符和重载函数
2、C++中的运算符重载（非常详细）
3、【原创】优先队列 priority_queue 详解
( •̀ ω •́ )✧点击这里，继续学习其他模块吧！
