文章目录
前言一、优先级队列概念及用法1.1 优先级队列概念1.2 优先级队列的使用1.2.1 对于内置类型1.2.2 对于自定义类型 二、小试牛刀三、优先级队列模拟实现3.1 优先队列模板参数与成员变量3.2 构造相关3.2.1 默认构造3.2.2 迭代器构造3.2.3 使用仿函数优化比较，实现大根堆与小根堆切换 3.3 其他功能实现3.3.1 push函数3.3.2 pop函数3.3.3 top、size和empty函数 四、仿函数4.1 仿函数概念4.2 优先队列中的模拟实现 总代码实现
前言
今天我们一起来学习优先级队列~~~<(￣︶￣)↗[GO!]
一、优先级队列概念及用法
1.1 优先级队列概念
优先队列是一种特殊的容器适配器，主要依赖堆的结构来保证元素按照特定的顺序进行操作。它的核心功能是确保队列的第一个元素总是最大或最小的元素，具体取决于堆的类型（大顶堆或小顶堆）。
| 功能 | 说明 |
|---|---|
| 容器适配器 | 优先队列是通过封装标准容器类（如vector或deque）实现的，作为底层数据存储。默认情况下使用vector。 |
| 类似堆的结构 | 优先队列与堆相似，支持随时插入元素，并且只能访问位于顶部的最大（或最小）元素。 |
| 算法支持 | 内部通过自动调用堆算法，如make_heap、push_heap和pop_heap，保持队列的堆结构。 |
| 随机访问迭代器 | 容器类应支持随机访问迭代器，如vector和deque，以便操作元素。 |
| 元素访问与修改 | 提供empty()、size()、top()等函数来操作和访问容器中的元素，元素总是从容器的“顶部”弹出。 |
常用接口与方法
| 方法 | 功能说明 |
|---|---|
| priority_queue() | 构造一个空的优先队列。 |
| empty() | 检测优先队列是否为空，空则返回true，否则返回false。 |
| size() | 返回优先队列中的元素个数。 |
| top() | 返回优先队列中最大的元素，即堆顶元素。 |
| push(x) | 向优先队列中插入元素x，并重新调整堆结构。 |
| pop() | 删除并移除优先队列中的最大元素，即堆顶元素。 |
优先队列通常使用vector作为底层存储结构，借助堆算法将vector中的元素构造成堆的形式。对于需要频繁使用堆的场景，优先队列是一个非常高效且方便的选择。注意，默认情况下优先队列是大顶堆，即top()返回的是当前最大的元素。
1.2 优先级队列的使用
1.2.1 对于内置类型
大根堆的使用
priority_queue<int> q;// 默认是大根堆，这里其实省略了三个模板参数，写完整是这样的// <优先级队列类型, 底层容器类型, 比较方式> 变量名;// priority_queue<int, vector<int>, less<int>> q;int: 队列中存储的数据类型。vector<int>: 底层容器类型，优先队列默认使用vector来存储数据。less<int>: 仿函数，用于定义优先队列的排序方式，默认是less<int>，表示大根堆（最大元素位于堆顶）。 在这里，priority_queue<int>实际上等价于priority_queue<int, vector<int>, less<int>>，即默认情况下优先队列是一个大根堆，也就是每次弹出最大值。
q.push(2);q.push(3);q.push(4);q.push(1);push()方法向优先队列中插入元素，队列会根据大根堆的规则自动调整顺序。插入顺序是2, 3, 4, 1。 while (!q.empty()) { cout << q.top() << " "; q.pop();}q.top()：返回堆顶元素（当前队列中的最大值）。q.pop()：移除堆顶元素，并重新调整堆结构。通过while循环依次输出并弹出堆顶元素，直到队列为空，输出顺序应该为4 3 2 1。 创建小根堆
#include // greater算法的头文件
priority_queue<int, vector<int>, greater<int>> q2;// 如果要建小根堆，也就是升序，要更改最后一个模板参数仿函数，也就是改变比较的方式greater<int>作为仿函数。 greater<int>：与less<int>相反，表示升序排列，即最小元素位于堆顶。 q2.push(2);q2.push(3);q2.push(4);q2.push(1);push()方法插入元素2, 3, 4, 1，此时优先队列会自动构造成小根堆。 while (!q2.empty()) { cout << q2.top() << " "; q2.pop();}while循环依次输出并弹出堆顶元素，直到队列为空，输出顺序应该为1 2 3 4。 总结
大根堆：默认情况下，priority_queue使用less<int>作为仿函数，即构建大根堆，每次弹出的是最大值。小根堆：通过指定greater<int>作为仿函数，可以构建小根堆，优先队列会自动将最小元素置于堆顶。 这里用deque也可以，不过我们在调整建堆是需要大量的随机访问，deque这方面是比较不行的，因此推荐适配器用vector就可以了。
这里还可以用迭代器区间来构造优先级队列。
void test_priority_queue02(){vector<int> v = { 1, 3, 5 ,2 ,9 };priority_queue<int> q(v.begin(), v.end());while (!q.empty()){cout << q.top() << " ";q.pop();}cout << endl;}1.2.2 对于自定义类型
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。
我们建议再自定义类型的内部进行operator<以及operator>，如果遇到实在无法再类内重载这些的情况，比如我传进来的日期类是一对指针，可以用一下的方法操作。
priority_queue<Date*, vector<Date*>, LessDate<Date*>> q;priority_queue<Date*, vector<Date*>, LessDate<Date*>>：构造了一个存储Date*类型的优先队列，并使用LessDate仿函数来进行排序。 使用自定义仿函数来处理指针类型（如Date*）的优先队列排序。默认情况下，priority_queue无法直接比较指针类型，因此需要通过自定义的仿函数LessDate来实现指针的解引用与比较。
template<class T>class LessDate {public: bool operator()(const Date* pd1, const Date* pd2) const { // 解引用指针并比较Date对象 return *pd1 < *pd2; }};LessDate类：这是一个仿函数，用于比较Date*类型的指针，内部通过解引用指针来比较Date对象的大小。重载operator()：定义了比较逻辑，仿函数在优先队列中用于排序。 
二、小试牛刀
数组中的第K个最大元素
class Solution {public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> q(nums.begin(), nums.end()); for (int i = 0; i < k - 1; i++) q.pop(); return q.top(); }};三、优先级队列模拟实现
3.1 优先队列模板参数与成员变量
通过上面的使用我们可以发现，优先队列需要三个模板参数
class T //类型, class Container = vector //适配器
class compare = less//仿函数用于建堆调整比较
而它的成员变量自然就是这个适配器
template<class T, class Container = vector<T>, class compare = less<T>>class priority_queue{public:private:Container _con;};3.2 构造相关
3.2.1 默认构造
默认构造，对于自定义类型，会去调_con的构造函数priority_queue() {}3.2.2 迭代器构造
template<class Iterator>priority_queue(Iterator first, Iterator last) { while (first != last) { _con.push_back(*first); ++first; } // 向下调整建堆 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) { AdjustDown(i); }}建堆主逻辑
通过迭代器范围[first, last)将元素添加到底层容器_con中。每个元素都被依次插入到容器中。在所有元素都插入后，接下来需要将这些元素调整为堆结构。通过对非叶子节点进行向下调整（调用AdjustDown），从最后一个非叶子节点开始，依次调整直到根节点。 向下调整
向下调整的主要逻辑在AdjustDown函数中实现。其主要目标是保持堆的性质（大根堆），具体步骤如下： 从父节点开始，计算其左子节点的位置。比较父节点与子节点（及其兄弟节点）的值，找到更大的子节点。如果父节点小于最大子节点，则交换二者，并继续向下调整。直到满足堆的性质（即父节点大于或等于子节点）为止。 时间复杂度分析
建堆的时间复杂度：在构造函数中，插入元素的时间复杂度为O(n)，因为每个元素都需要被添加到底层容器中。向下调整的时间复杂度：AdjustDown的时间复杂度为O(log n)，每次调用会最多经过树的高度（log n）进行比较和交换。由于我们需要从每个非叶子节点向下调整，整体建堆的复杂度为O(n)。 
private://向下调整建堆void AdjustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆，降序排列，因此要找孩子中大的那一个if (child + 1 < _con.size() && _con[child] < _con[child + 1])child++;if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}public://默认构造，对于自定义类型，会去调_con的构造函数priority_queue() {}//支持迭代器//迭代器也要写成模板template<class Iterator>priority_queue(Iterator first, Iterator last){while (first != last){_con.push_back(*first);++first;}//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}3.2.3 使用仿函数优化比较，实现大根堆与小根堆切换
在前面的代码中，我们直接将比较的方法写死了。
如果我们要实现小根堆呢？要重新再写一个函数吗？
答案是不用，我们可以使用一个仿函数，重新定义比较，传什么仿函数就用什么比较。
这里要注意的是，因为我们仿函数代表的仅仅是一种<或>，因此我们再写的时候要把符号关系搞成一致，像这样：
//向下调整建堆void AdjustDown(int parent){//仿函数定义一个对象出来，用它来替换比较Compare com;int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆，降序排列，因此要找孩子中大的那一个if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))child++;if (com(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}3.3 其他功能实现
3.3.1 push函数
void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1);}x插入到优先队列中。过程： 首先将元素x添加到容器_con的尾部。然后调用AdjustUp函数，从新插入元素的位置向上调整，确保堆的性质被保持（大根堆）。 3.3.2 pop函数
void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0);}_con[0]）与堆尾元素交换。删除堆尾元素。通过调用AdjustDown函数，从堆顶开始向下调整，保持堆的性质。 3.3.3 top、size和empty函数
top：返回堆顶元素，即优先队列中优先级最高的元素。size：返回优先队列中元素的数量。empty：检查优先队列是否为空。 向上调整 (AdjustUp)
//向上调整void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}while循环中，如果子节点的值大于父节点的值，则进行交换。更新child和parent的值，继续向上调整，直到不再需要交换或达到根节点。 四、仿函数
4.1 仿函数概念
仿函数（Functor）是一个重载了 operator() 的类或结构体，能够像函数一样被调用。它们常用于需要自定义比较、处理或操作的数据结构和算法中，比如在 STL 容器、算法中作为参数传递。
仿函数的优势在于：
可以持有状态：仿函数的对象可以保存数据，允许使用构造函数初始化。语义明确：通过命名类，能够清晰表达意图。以下是一个简单的仿函数例子:
#include <iostream>using namespace std;// 定义一个仿函数类class Compare {public: // 重载运算符() bool operator()(int a, int b) const { return a < b; // 返回true表示a小于b }};int main() { Compare compare; int x = 5, y = 10; // 使用仿函数进行比较 if (compare(x, y)) { cout << x << " is less than " << y << endl; } else { cout << x << " is not less than " << y << endl; } return 0;}输出
5 is less than 10Compare 类实现了一个仿函数，通过重载 operator() 来比较两个整数。通过创建 Compare 的对象并调用它，就可以像使用普通函数一样进行比较。
4.2 优先队列中的模拟实现
//仿函数模拟实现/函数对象template<class T>class Less{public:bool operator() (const T& a, const T& b){return a < b;}};template<class T>class Greater{public:bool operator() (const T& a, const T& b){return a > b;}};总代码实现
以下是优先队列中大根堆和小根堆的对应关系，以及根节点的最大和最小属性：
| 堆类型 | 比较方式 | 仿函数 | 根节点 |
|---|---|---|---|
| 大根堆 | > | std::less<T> | 最大 |
| 小根堆 | < | std::greater<T> | 最小 |
#pragma once#include<vector>namespace jyf{//仿函数模拟实现/函数对象template<class T>class Less{public:bool operator() (const T& a, const T& b){return a < b;}};template<class T>class Greater{public:bool operator() (const T& a, const T& b){return a > b;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{private://向下调整void AdjustDown(int parent){//仿函数定义一个对象出来，用它来替换比较Compare com;int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆，降序排列，因此要找孩子中大的那一个if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))child++;if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}//向上调整void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}public://默认构造，对于自定义类型，会去调_con的构造函数priority_queue() {}//支持迭代器//迭代器也要写成模板template<class Iterator>priority_queue(Iterator first, Iterator last){while (first != last){_con.push_back(*first);++first;}//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void push(const T& x){//先放到堆尾_con.push_back(x);//进行向上调整AdjustUp(_con.size() - 1);}void pop(){//先交换第一个和最后一个swap(_con[0], _con[_con.size() - 1]);//删除堆尾_con.pop_back();//向下调整AdjustDown(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_priority_queue1(){// 默认是大堆 -- less//priority_queue<int> pq;// 仿函数控制实现小堆priority_queue<int, vector<int>, Greater<int>> pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}}到这里就结束啦，谢谢大家!!!??????○( ＾皿＾)っHiahiahia…
