👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：C++航路
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨
一、priority_queue的介绍
- 优先级队列顾名思义就是按优先级出队列
-
priority_queue是一个容器适配器，默认使用vector作为其底层存储数据的容器 -
priority_queue在vector上使用了堆heap的算法将vector中元素构造堆的结构，默认情况下是大堆。（如何构造成小堆在【仿函数】会讲解到）
二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢
首先优先级队列priority_queue的适配器也可以用deque，但是没有必要。
我们在上篇博客总结了deque的缺点：
因此，可以得出priority_queue不选择deque作为默认适配器如下：
- 优先级队列的底层是一个堆，则需要频繁访问和处理最高优先级元素（保持大堆或小堆性质）。相比之下，
vector更胜一筹 -
deque实际的底层存储空间不是连续的，因此在使用时需要更多的空间，可能会导致空间的浪费。
三、priority_queue的常见操作
#include <iostream>
#include <queue>
using namespace std;
// priority_queue的常见操作
int main()
{
// 默认是大堆
priority_queue<int> pq;
pq.push(3);
pq.push(5);
pq.push(1);
pq.push(4);
pq.push(0);
while (!pq.empty())
{
cout << pq.top() << ' ';
pq.pop();
}
cout << endl;
return 0;
}
【输出结果】
注意：优先级队列也是不支持迭代器遍历的！！！
四、模拟实现priority_queue
4.1 构造函数（迭代器区间构造 + 无参默认构造）
namespace wj
{
template<class T, class container = vector<T>>
class priority_queue
{
private:
void AdjustDown(int parent)
{
// 默认是大堆
// 假设左孩子最大
size_t 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[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
public:
// 无参默认构造
priority_queue()
{}
// 带区间的构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
// 插入数据
while (first != last)
{
_con.push_back(*first);
++first;
}
// 建堆操作 (默认是大堆)
// _con.size() - 1是为了找到第一个叶子结点
// (整体再-1) / 2是为了找到最后一个非叶子结点
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
// 向下跳整建堆
AdjustDown(i);
}
}
private:
container _con;
};
}
插入一个数据，由于还要保持大堆的性质，如果尾插的结点要比其父结点大，就要进行 向上调整
参考博客：点击跳转
4.2 删除堆顶元素pop
void pop()
{
// 头尾结点交换后，再删除
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
// 最后以堆顶元素向下继续建堆
AdjustDown(0);
}
4.3 插入push
namespace wj
{
template <class T, class Container = vector<T>>
class priority_queue
{
private:
// 向上调整
void AdjustUp(int child)
{
// 找到父亲
int parent = (child - 1) / 2;
while (child > 0)
{
// 保持大堆性质
if (_con[parent] < _con[child])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
public:
void push(const T &val)
{
// 尾插
_con.push_back(val);
// 再以最后一个叶子结点向上调整建堆
AdjustUp(_con.size() - 1);
}
private:
Container _con;
};
}
4.4 获取堆顶元素top
const T& top() const
{
return _con[0];
}
4.5 判断是否为空empty
bool empty() const
{
return _con.empty();
}
4.6 获取个数大小size
size_t size() const
{
return _con.size();
}
五、仿函数
5.1 什么是仿函数
仿函数（函数对象）简单来说：一个类中重载operator()，并且这个类实例化的对象可以像函数一样使用，实现了类似函数的行为。
例如，定义一个加法仿函数可以这样实现：
struct Add
{
int operator()(const int a, const int b) const
{
return a + b;
}
};
int main()
{
// 实例化
Add add;
int result = add(3, 5); // 调用仿函数
cout << "add(3, 5) = " << result << endl;
return 0;
}
在上面的例子中，Add是一个仿函数，它重载了函数调用运算符 operator()，使得add对象可以像函数一样被调用。通过add(3, 5)，我们可以得到结果8
- 在C++ 中，仿函数是一种灵活且强大的编程工具，常常用于算法和标准库中的函数对象。
就比如说sort函数，默认排的是升序
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = { 5,1,4,2,0,3 };
int arrSize = sizeof(arr) / sizeof(arr[0]);
// less<int> 默认可以不写
sort(arr, arr + arrSize, less<int>());
for (int i = 0; i < arrSize; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
return 0;
}
【输出结果】
less是库里提供的，其作用就是用于小于不等式比较的函数对象类
那么如果想排降序，可以将less替换成greater，这也是库里提供的，其作用是用于大于不等式比较的函数对象类
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = { 5,1,4,2,0,3 };
int arrSize = sizeof(arr) / sizeof(arr[0]);
// less<int> 默认可以不写
sort(arr, arr + arrSize, greater<int>());
for (int i = 0; i < arrSize; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
return 0;
}
【输出结果】
注意：如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供>或者<的重载。文章来源：https://www.toymoban.com/news/detail-688224.html
六、实现priority_queue的仿函数（源码）
以上我们实现的是的优先级队列是大堆性质（默认），我们可以通过增加模板参数来实现大堆小堆秒切换。文章来源地址https://www.toymoban.com/news/detail-688224.html
namespace wj
{
template<class T, class container = vector<T>, class Compare = less<T>>
class priority_queue
{
private:
void AdjustDown(int parent)
{
// 实例化
Compare com;
size_t 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[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
void push(const T& val)
{
_con.push_back(val);
AdjustUp(_con.size() - 1);
}
const T& top() const
{
return _con[0];
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
container _con;
};
}
到了这里，关于【C++初阶】模拟实现优先级队列priority_queue的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[C++历练之路]优先级队列||反向迭代器的模拟实现](https://imgs.yssmx.com/Uploads/2024/02/755976-1.png)
