网站建设验收标准东莞百度推广优化
优先队列(priority_queue)
优先队列是一种特殊的队列,它同一般队列一样,都支持先入先出的规则,但不同于一般队列的是,它对存储的数据有着自己独特的存储风格。
priority_queue<int>pa;pa.push(1);pa.push(2);pa.push(3);pa.push(4);pa.push(5);int n = pa.size();for (int i = 0;i <n ;i++){cout << pa.top() << " ";pa.pop();}cout << endl;return 0;
代码运行结果为 5, 4, 3, 2, 1,由此可见,我们发现优先队列中的数据按一定的规则排序
优先队列是一个模板类,拥有三个模板参数
- T为存储的数据类型
- Container为容器,如list,vector等,决定了优先队列中数据的存储方式
- Compare为比较方法, 它对存储的数据进行排序提供比较方法
优先队列的模板参数中,除了第一个数据类型没有缺省值,其他两个均有缺省值,也代表在实际使用中,我们不显示写出后两个模板参数也可以。
优先队列会对每一个存进的数据进行排序,这类似于我们之前学习的一个数据结构,也就是堆,它会对新加入的数据元素进行向上调整,也是排序,堆有大堆和小堆,同样,优先队列也有。
priority_queue<int>q;//大堆
priority_queue<int, vector<int>, less<int>> q; // 大堆
priority_queue<int, vector<int>, greater<int>> q; // 小堆
less代表的是大堆,greater代表的是小堆,和我们日常的认知相违背,我们记住就好,c++就是这么定义的(less和greater是c++中的两个比较函数)
优先队列的接口
- top()取出队头元素
- pop()删除队头元素
- push()添加队元素,并按照一定比较方法,与前面的数据比较,找到自己的新位置
- empty()判断优先队列是否为空
优先队列的实现
namespace Yu
{template<class T>class Less//我要用这个仿函数建立大堆,契合c++,父亲大于孩子{public:bool operator()(T& x, T& y){return x < y;}};template<class T>class Great//用这个建立小堆,父亲小于孩子{public:bool operator()(T& x, T& y){return x > y;}};template<class T,class continer=vector<T>,class compre=less<T>>class priority_queue{public:void AdjustUp( size_t child){compre 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;}else{break;}}}void Adjust_Down( size_t parent){compre 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;}else{break;}}}size_t size(){return _con.size();}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}T& top(){return _con[0];}void pop(){int end = _con.size() - 1;swap(_con[0], _con[end]);_con.pop_back();Adjust_Down(0);}private:continer _con;};
}
由先前的介绍,我们可以知道优先队列存储数据的形式类似于堆,所以,我们在实现优先队列的时候,基本上就是手撕堆,但也不是原搬堆。
首先,我们因为需要存储多种类型的数据,不可能仅仅针对某一个数据类型创建单独的数据结构去针对它,所以,我们一般用模板
template<class T,class continer=vector<T>,class compre=less<T>>
class priority_queue如上所示,贴合stl中的优先队列,我们也给我们的优先队列三个模板参数,第一个是我们存储的数据类型,第二个是我们的容器,第三个是比较方法,用来切换大堆小堆模式
接口实现
1.push()
void AdjustUp( size_t child){compre 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;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}
当我们push进一个数据元素,它就要与前面已经存储的数据元素进行排序,找到自己的位置,就和堆一样,每进入一个新数据,就要进行向上调整,向上调整和向下调整前提都是建立在已经是堆的基础上,但我们这里不需要考虑,因为每次数据进入前,之前的数据已经是堆了,第一个数据默认是堆。
我们这里的向上调整函数只用传一个参数,原因是我们的成员变量可以被成员函数随意访问,并且我们的成员变量是容器,它本身也可以调用一些函数来获取自身的大小。
2.pop()
void Adjust_Down( size_t parent){compre 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;}else{break;}}}
void pop(){int end = _con.size() - 1;swap(_con[0], _con[end]);_con.pop_back();Adjust_Down(0);}
删除数据,同堆一样,为了最求效率化,将最末尾的数据和头部数据进行值交换,如何在使堆的大小减一,并采用向下调整的方式重新排列,使其再次成为新的堆,不过这次的头部数据,是比之前的头部数据小或者大的第二数据,向下调整的基础是本身是堆,这里符合条件,故可以用向下调整。
3,top()
T& top(){return _con[0];}
很简单的一段代码,得益于容器本身的多功能性
4.empty()
bool empty()
{return ——con.empty();
}
仿函数的介绍
我们之前提到优先队列模板参数中,需要传输比较方法,但模板参数只能传输一个类型,不能传递函数,这里就需要用到仿函数
所谓的仿函数,就是模拟函数,它是利用模板类和重载符合运算符来实现的,具体看代码
template<class T>class 类名{返回类型 operator()(参数列表){函数体; }};
这就是一个仿函数的基本书写形式,用模板类是使其更加灵活,能够处理更多的数据类型,平常定义的时候,我们需要根据想要的功能,来书写函数体,调用的时候直接创建一个类对象
类对象(参数列表)
这就是仿函数的调用形式。
仿函数的优越性在于简单,与自定义,你可以根据你的需求去书写函数体,用他实现你的功能,然后可以根据模板参数选择要处理的数据类型。
注意:我们一般将类名与要实现的功能联系起来,这样可以提高代码的可读性。