优先级队列的基本使用
模拟实现上面的接口函数，优先级队列不是队列，而是类似一个堆一样的东西，我们先来试试它的接口函数是怎么个样子的。
需要包含的头文件是queue。
#include<iostream>
#include<queue>
using namespace std;
void priority_queuetest1()
{
priority_queue<int> pq;
pq.push(2);
pq.push(1);
pq.push(4);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}
int main()
{
priority_queuetest1();
return 0;
}
这就是我们的基本使用方法，但是我们运行我们的代码之后发现的打印结果不是升序的
打印结果· ： 4 3 2 1
这里就要说明一个问题，我们建立的堆是大堆，也就导致了最后的打印结果就是降序，这个地方会出现一个叫仿函数的东西，我们在后面进行模拟实现的时候回来看到这个。
需要记住小于是大堆，大于是小堆！！！！（后面会解释）
我们的sort排序也是这个样子的。
如果我们用sort对我们的排序要进行排序的时候，默认是升序，原因就是我们进行传仿函数的时候传的是less，我们可以来看看sort的文档。
这里我们传的就是一个对象，而上面的优先级队列传的不是对象，而是模板参数，这里需要注意一下，我们假如要排一个 vector的升序。代码如下。
vector<int> v = { 6,5,4,3,2,1 };
sort(v.begin(), v.end());
for (auto e : v)
{
cout << e << " ";
}结果 ： 1 2 3 4 5 6
如果要排降序的话就需要传一个参数就是仿函数过去。准确来说是对象，而我们上面的优先级队列是类型，编译器会自动去推算！！！！
使用如下
vector<int> v = { 6,5,4,3,2,1 };
sort(v.begin(), v.end(),greater<int>());
for (auto e : v)
{
cout << e << " ";
}6 5 4 3 2 1
那如果我们要进行的是小堆呢，就可以这样使用。
void priority_queuetest1()
{
priority_queue<int,vector<int>,greater<int>> pq;
pq.push(2);
pq.push(1);
pq.push(4);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
/*vector<int> v = { 6,5,4,3,2,1 };
sort(v.begin(), v.end(),greater<int>());
for (auto e : v)
{
cout << e << " ";
}*/
}这里C语言和C++的区别 ，C语言是没有仿函数的，他是用函数指针来进行调用的。比如qsort函数就是这样的。
仿函数
1 ：仿函数其实就是一个类，只要我们在类里面重载了运算符括号，这个类我们就可以认定为具有仿函数功能！
2 ： 它的对象可以像函数一样去调用。
3 ： 写成模板的时候，那么我们任意数据都可以来进行使用。
那如果我们要写一个最基本的仿函数是怎么个样子，首先就是它得是一个类，是不是要写成模板，取决于你自己。
void priority_queuetest2()
{
struct Less//区别于库里面
{
bool operator()(const int& x, const int& y)
{
return x < y;
}
};
Less com;
cout << Less()(1, 2) << endl;
cout << com(5, 2) << endl;
cout << com.operator()(3,1) << endl;
}模拟实现队列
我们先实现一个不加上仿函数的优先级队列，根据文档里的接口先来实现一些push， 我们的堆是怎么进行push的呢？？
因为我们的堆其实就是一个满二叉树的结构，那在数组里其实就是尾插进去一个数，但是尾插进去之后，可能就不是满二叉树了，所以要做的就是向上调整。
优先级队列的插入push
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}push的之后就需要进行向上调整，在这里我们是用了其他容器来进行实现的，因为二叉树是共和数组，所以这里的默认容器就是vector。
需要进行的是向上调整，在我的文章堆里面是讲过这个的，大家可以跳转到下面的这个链接当中
https://blog.csdn.net/2301_76895050/article/details/134611394?spm=1001.2014.3001.5501
向上调整
void adjust_up(size_t child)
{
size_t 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;
}
}
}还有就是pop，我们需要注意的是pop不是pop尾部的数据，而是数组下标是0位置二的，我们只需要先交换头和尾位置的数据，然后再进行删除，这个时候把头部的数据删掉了，但是却不是二叉树，这个时候（默认是大堆）堆顶的数据不是最大的，所以需要做的就是向下进行调整。
优先级队列的pop
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}向下调整
void adjust_down(size_t parent)
{
size_t child = 2 * parent + 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 = 2 * parent + 1;
}
else
{
break;
}
}
}其他接口函数都是对我们的容器进行一个封装，所以大体框架就是下面的这个
template<class T,class Container = vector<T>>
class priority_queue
{
public:
//默认是大堆
void adjust_up(size_t child)
{
size_t 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;
}
}
}
void adjust_down(size_t parent)
{
size_t child = 2 * parent + 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 = 2 * parent + 1;
}
else
{
break;
}
}
}
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
T top()
{
return _con[0];
}
private:
Container _con;
};写完一个代码就需要进行测试一下，我们可以插入一下数据，看看是不是大堆，然后打印我们的数据，来看看是不是有序的就行了、
测试代码
void priority_queuetest1()
{
priority_queue<int> pq;
pq.push(5);
pq.push(2);
pq.push(1);
pq.push(4);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}检查我们的代码的时候其实是可以先来看插入的逻辑的，看看插入之后是不是建立成大堆，如果建立堆问题出错了，就只要两个地方会有问题，一个就是我们插入逻辑，插入逻辑一般不会有问题的，可能再传参数的地方有问题，还有就是我们的向上调整是不是存在一些逻辑问题。
重新认识仿函数
如何控制比较逻辑呢，我们这里默认建立的是大堆，我们需要通过仿函数来进行更改比较逻辑，仿函数最大逻辑就是，对象可以像函数那样进行比较。
快速实现仿函数。
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};因为是类，我们可以传递模板参数。所以先来改变优先级队列的参数，要在加上一个仿函数的类模板
所以我们只是需要在我们的函数里面定义一个对象。
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T,class Container = vector<T>,class Compare = less<T>>
class priority_queue
{
public:
//默认是大堆
void adjust_up(size_t child)
{
Compare com;
size_t 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;
}
}
}
void adjust_down(size_t parent)
{
Compare com;
size_t child = 2 * parent + 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 = 2 * parent + 1;
}
else
{
break;
}
}
}
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
T top()
{
return _con[0];
}
private:
Container _con;
};
void priority_queuetest1()
{
priority_queue<int> pq;
pq.push(5);
pq.push(2);
pq.push(1);
pq.push(4);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}优势1 ： 只要更改仿函数就能更改我们的比较逻辑 大堆也就变成小堆
优势2 ： 是一个类，理解起来和写起来都比较方便，c语言要实现这样只能通过函数指针，函数指针是个比较麻烦的东西
完整代码
namespace tjl
{
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T,class Container = vector<T>,class Compare = less<T>>
class priority_queue
{
public:
//默认是大堆
void adjust_up(size_t child)
{
Compare com;
size_t 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;
}
}
}
void adjust_down(size_t parent)
{
Compare com;
size_t child = 2 * parent + 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 = 2 * parent + 1;
}
else
{
break;
}
}
}
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
T top()
{
return _con[0];
}
private:
Container _con;
};
void priority_queuetest1()
{
priority_queue<int,vector<int>,greater<int>> pq;
pq.push(5);
pq.push(2);
pq.push(1);
pq.push(4);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}
}补充
仿函数的作用可不只是这样嗷，我们如果要来比较一下我们的日期应该是怎么来实现呢。
class Date
{
public:
friend ostream& operator<<(ostream& _cout, const Date& d);
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}这个时候因为我们假设比较Date，当然我们日期也可以使用之前的方式来进行比较，这是这个时候的比较类型是自定义的。
代码如下
void priority_queuetest2()
{
priority_queue<Date> pq;
pq.push({2023,1,3});
pq.push({2013,1,7});
pq.push({2034,3,1});
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}但是如果我们现在要进行的是Date*的比较呢，这个时候就不可了，首先比较的时候重载必须是自定义的类型，内置类型是不能进行重载的，比较逻辑就是不正确的，所以这个时候要在写一个仿函数
class GreaterPDate
{
public:
bool operator()(const Date* p1, const Date* p2)
{
return *p1 > *p2;
}
};以上就是今天的分享，我们下篇文章再见!!!
