优先队列 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       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] <= 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 详解

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