网站建设验收标准网络营销就是

优先队列（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，由此可见，我们发现优先队列中的数据按一定的规则排序 

 

优先队列是一个模板类，拥有三个模板参数

1. T为存储的数据类型
2. Container为容器，如list，vector等，决定了优先队列中数据的存储方式
3. 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++中的两个比较函数）

 优先队列的接口

1.  top（）取出队头元素
2. pop（）删除队头元素
3. push（）添加队元素，并按照一定比较方法，与前面的数据比较，找到自己的新位置
4. 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()(参数列表){函数体;   }};

这就是一个仿函数的基本书写形式，用模板类是使其更加灵活，能够处理更多的数据类型，平常定义的时候，我们需要根据想要的功能，来书写函数体，调用的时候直接创建一个类对象

类对象（参数列表） 

这就是仿函数的调用形式。

仿函数的优越性在于简单，与自定义，你可以根据你的需求去书写函数体，用他实现你的功能，然后可以根据模板参数选择要处理的数据类型。

注意：我们一般将类名与要实现的功能联系起来，这样可以提高代码的可读性。