优先队列 priority_queue详解

 说到，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 <= 105
• k 的取值范围是 [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] <= 104
• 1 <= 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 详解

---

( •̀ ω •́ )✧点击这里，继续学习其他模块吧！