priority_queue简介
优先级队列的底层结构其实就是堆，就是我们在学习二叉树的时候学习的堆。它是一种逻辑结构，底层还是vector ，我们把它想象成一个堆结构。
我们在学习堆的时候，知道了它的父亲和左右孩子的关系。
它如果存在孩子，则一定存在这一种关系，leftchilde=2*parent+1;rightchilde=2*parent+2; 这些都分别对应着它们的下标。
为什么叫做堆呢，我们下面来看一下。
我们可以看到，左边的是大顶堆，右边的是小顶堆。观察一下它们有什么特点呢。
我们再前面讲过二叉树的性质，其实堆实际上就是一颗完全二叉树，并且可以发现，大顶堆的双亲节点都比它的左右孩子要大，小顶堆的双亲节点都要比它的左右孩子要小。
其实它们的物理结构还是一个数组，只是我们把他们的关心想象成为一颗二叉树，因为完全二叉树特有的性质，它的双亲节点的下标和它们的各自的左右孩子下标都有关系。
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子节点的值，叫大顶堆（左上图），或者每个节点的值都小于或等于其左右孩子节点的值，叫小顶堆（右上图）。
注意，这个树的根节点一定是最大的，较大的数相对来说要靠上面一点。
下面我们来模拟实现一下priority_queue。
模拟实现之前，我们还需要了解一下向上调整算法，和向下调整算法。
向下调整算法
向下调整算法就是用双亲节点和左右孩子比较，我们这里以建大堆为例，如果双亲节点小于孩子节点，就将双亲节点的值和孩子节点的值交换，然后让父亲做孩子，再去找父亲的父亲，依次比较，直到最后到根节点。
//向下调整函数
void AdjustDown(int* arr, int size, int root)
{
//父亲就根节点
int parent = root;
//根据父亲找到左孩子
int child = parent * 2 + 1;
//当孩子小于数组长度时
while (child < size)
{
//如果左孩子小于右孩子，则将孩子默认为右孩子
if (child + 1 < size && arr[child] < arr[child + 1])
{
child += 1;
}
//如果孩子比父亲大，则交换值，再将父亲的值给孩子
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
}
parent = child;
child = parent * 2 + 1;
}
}上面这个是使用C语言实现的，我们使用C++实现的时候，由于是使用vector实现的，所以说我们就不会那么复杂。
向上调整算法
每当我们要插入一个值的时候，我们都需要将整个数组变成一个堆，这个时候就需要使用到向上调整算法，因为每一个数都在数组的尾部，所以说我们每次都从插入的那一个数开始进行向上调整，因为我们再插入之前，整个vector就已经是堆了，所以我们只需要将最后一个值与它的祖先一一比较就行了。
void adjustup()
{
//默认孩子是最后一个数
int childe = con.size() - 1;
//通过孩子与父亲之前的关系，找到父亲节点
int parent = (childe - 1) / 2;
while (childe > 0)
{
//默认是升序，建小堆
//如果父亲比孩子小，就交换位置
if (com(con[parent], con[childe]))
{
swap(con[childe], con[parent]);
//再更新孩子父亲的下标
childe = parent;
parent = (childe - 1) / 2;
}
//否则就跳出循环
else
{
break;
}
}
}仿函数
由于我们在比较的时候，有可能是升序，有可能是降序，但是我们又不可能写两个排序。我们应该根据用户的需要，提供对应的升序和降序。怎么样在同一个函数中达到这样的要求呢。我们就必须要使用仿函数。
仿函数本质就是一个类。
它的类成员函数里面，重载了一个 operator() 。它其实就是用来比较大小的。
我们先来看一看它们长什么样。
//排升序的仿函数
template <class T>
class Less
{
public:
bool operator()(const T& x, const T& 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 Less
{
public:
bool operator()(const T& x, const T& 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=vector<T>, class compare = Less<T>>
class priority_queue
{
public:
void adjustdown(int parent)
{
int childe = 2 * parent + 1;
while (childe < con.size())
{
if (childe + 1 < con.size() && com(con[childe], con[childe + 1]))
{
childe++;
}
if (com(con[parent], con[childe]))
{
swap(con[childe], con[parent]);
}
parent = childe;
childe = 2 * parent + 1;
}
}
void adjustup()
{
//默认孩子是最后一个数
int childe = con.size() - 1;
//通过孩子与父亲之前的关系，找到父亲节点
int parent = (childe - 1) / 2;
while (childe > 0)
{
//默认是升序，建小堆
//如果父亲比孩子小，就交换位置
if (com(con[parent], con[childe]))
{
swap(con[childe], con[parent]);
//再更新孩子父亲的下标
childe = parent;
parent = (childe - 1) / 2;
}
//否则就跳出循环
else
{
break;
}
}
}
bool empty() const
{
return con.empty();
}
size_t size() const
{
return con.size();
}
T& top()
{
return con[0];
}
void push(const T& x)
{
con.push_back(x);
adjustup();
}
void pop()
{
assert(!con.empty());
swap(con[0], con[con.size() - 1]);
con.pop_back();
adjustdown(0);
}
private:
container con;
compare com;
};整个代码还是比较简单的，就是我们需要了解堆这个结构，然后其它的一些接口也是比较简单的，我们同样的是使用了容器适配器模式。
