优先级队列的实模拟实现

优先级队列底层默认用的是vector来存储数据，实现了类似我们数据结构中学习过的堆的队列，他的插入和删除都是优先级高先插入和删除。下面我们来模拟实现它们常见的接口来熟悉优先级队列。

仿函数

在介绍优先级队列之前，我们先熟悉一个概念，叫做仿函数，顾名思义，仿函数不是函数，它的底层是一个类，类中public部分实现（）重载，使得我们可以像调用函数一样调用它，因此我们叫它为仿函数。有了仿函数，我们可以泛型书写代码实现更便捷的代码。

函数特化

函数模板的特化步骤：

1. 必须要先有一个基础的函数模板

2. 关键字 template 后面接一对空的尖括号 <>

3. 函数名后跟一对尖括号，尖括号中指定需要特化的类型

4. 函数形参表 :  必须要和模板函数的基础参数类型完全相同，如果不同编译器可能会报一些奇

怪的错误。

	template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>//偏特化,当传的是指针的时候，我们可以调用它的解引用来比较，因为大部分情况下比较地址的意义比较小class less<T*>{public:bool operator()(const T* const& x, const T* const& y){return *x < *y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};

全特化

全特化是将函数的模版参数全部确定，就是将T全部指定。具体实现方式如下：

template<class T1, class T2>
class Data
{
public:
Data() {cout<<"Data<T1, T2>" <<endl;}
private:
T1 _d1;
T2 _d2;
};
template<>
class Data<int, char>
{
public:
Data() {cout<<"Data<int, char>" <<endl;}
private:
int _d1;
char _d2;
};

这里指定T的类型为int和char就是全特化。

偏特化

部分特化

将模板参数类表中的一部分参数特化。

将第二个参数特化为int，第二个参数不特化
template <class T1>
class Data<T1, int>
{
public:
Data() {cout<<"Data<T1, int>" <<endl;}
private:
T1 _d1;
int _d2;
};

参数更进一步的限制

对函数T的类型进一步进行限制。

//两个参数偏特化为指针类型
template <typename T1, typename T2>
class Data <T1*, T2*>
{
public:
Data() {cout<<"Data<T1*, T2*>" <<endl;}
private:
T1 _d1;
T2 _d2;
};

其次，我们可以看到第二个less我们实现时在类名后加了<T*>，这是偏特化的实现，C++支持这种语法是因为当我们T被实例化为地址时，我们比较它们的地址大部分是没有意义的，所以我们要特指当T被实例化为T*时，我们调用偏特化的仿函数，其中T仍然为类型，这样便于我们修改T。

最后，偏特化的匹配规则是有现成实现的吃现成的，没有现成的才去实例化实现。

优先级队列模拟实现

了解一个前置知识后，我们来模拟实现优先级队列进行熟悉代码，了解底层。

整体框架

template<class T, class Container, class Compare = less<T>>
class priority_queue
{
public:private:Container _con;
};

构造函数

先实现构造函数，构造函数我们利用了别的现有的容器来实现，编译器会自动调用这个容器中的构造函数，所以我们不需要进行显示实现。

priority_queue()//为什么是空构造
{}

尾插 

由于优先级队列是按堆的形式建立的，需要进行向上调整和向下调整来实现大堆或者小堆。

利用vector中的push_back实现尾插，然后在尾插的部分进行向上调整。

void push(const T& x)
{_con.push_back();adjustup(_con.size()-1);
}

删除

由于按堆实现，我们不能直接进行删除，为了不干扰整个堆的结构，我们把头删的元素与最后一个元素进行交换，然后进行向下调整即可。

void pop()
{std::swap(_con[0], _con[_size - 1]);_con.size() = _con.size() - 1;
/*	_con.pop_back();*/adjustdown(0);
}

top取堆顶元素

这个比较简单，我们直接取堆顶元素即可。

	const T& top() const//取栈顶元素{return _con[0];}

判空

我们利用现有的vector容器进行判空即可，可以进一步理解栈和队列的实现方式。它们实现方式都是类似的，都是利用了现有的容器进行的。

bool empty() const//判断空
{if (_con.size() == 0)return true;else return false;
}

返回元素个数

也是一样，利用现有容器的size()函数进行实现。

	size_t size() const{return _con.size();}

向下调整和向上调整

我们不对外提供向上调整和向下调整的接口，所以把它设为私有函数。

知道孩子求父亲是（child-1）/2是父亲的下标，默认建大堆的情况，如果父亲小于孩子，父亲孩子交换，父亲下标赋值给孩子下标，然后再根据孩子下标求父亲小标再次进比较直到堆顶。

向下调整是知道堆顶元素向下调整，知道父亲求孩子是parent*2+1，求下来是左孩子节点，由于堆顶要最大的元素，所以我们在保证右孩子存在的情况下判断左右孩子的大小，然后和向上调整一样进行操作即可。

private:void adjustup(int child)//向上调整要给下标进行下标访问调整{Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);// 父亲大父亲向上调整child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(int parent)//同理，向下调整要给下标进行下标访问建大堆{//目标就是把最大的往上放，即父节点为maxint child = parent * 2 + 1;//左孩子while (child<_con.size()){if (chile + 1 < _con.size() && _con[child] < _con[child + 1]){//保证右孩子存在的情况下，右孩子大的话让右孩子向上调整child++;}if (_con[parent] < _con[child]){swap(_con[parent] < _con[child]);/*	child = parent;parent = parent * 2 + 1;*/parent = child;child = parent * 2 + 1;}}}

最后我们给出整个优先级队列的实现方式：

#pragma once
#include<vector>
namespace bit//仿函数，其实是类，内部进行重载，可以像类一样被调用
{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>//偏特化,当传的是指针的时候，我们可以调用它的解引用来比较，因为大部分情况下比较地址的意义比较小class less<T*>{public:bool operator()(const T* const& x, const T* const& y){return *x < *y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container, class Compare = less<T>>class priority_queue{public:priority_queue()//为什么是空构造{}void push(const T& x){_con.push_back();adjustup(_con.size()-1);}void pop(){std::swap(_con[0], _con[_size - 1]);_con.size() = _con.size() - 1;/*	_con.pop_back();*/adjustdown(0);}const T& top() const//取栈顶元素{return _con[0];}bool empty() const//判断空{if (_con.size() == 0)return true;else return false;}size_t size() const{return _con.size();}private:void adjustup(int child)//向上调整要给下标进行下标访问调整{Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);// 父亲大父亲向上调整child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(int parent)//同理，向下调整要给下标进行下标访问建大堆{//目标就是把最大的往上放，即父节点为maxint child = parent * 2 + 1;//左孩子while (child<_con.size()){if (chile + 1 < _con.size() && _con[child] < _con[child + 1]){//保证右孩子存在的情况下，右孩子大的话让右孩子向上调整child++;}if (_con[parent] < _con[child]){swap(_con[parent] < _con[child]);/*	child = parent;parent = parent * 2 + 1;*/parent = child;child = parent * 2 + 1;}}}private:Container _con;};}