priority_queue的使用和介绍
priority_queue的介绍
优先级队列（priority_queue）它也是一个容器适配器，默认使用的容器是vector，在往队列中放入数据时，它会将容器中放置的数据通过堆算法调整成 大堆/小堆，在使用时我们若不指定建堆方法，它默认会是排大堆（less）
它的使用方法其实和stack，queue类似，只是priority_queue在插入元素的基础上进行了调整建堆
priority_queue的定义方式
1.使用priority_queue创建大堆对象：
priority_queue<int, vector<int>, less<int>> q1;2.使用priority_queue创建小堆对象:
priority_queue<int ,vector<int>, less<int>> q2;3.不指定容器和底层使用的堆算法
priority_queue<int> q3;这时它的容器和堆算法默认使用的是vector<int>和less<int>
priority_queue的接口展示：
| 成员函数 | 功能 |
| push | 向队尾插入一个元素，并向上调整排序 |
| pop | 删除堆顶元素(首尾元素交换，删除队尾元素，首元素向下调整) |
| top | 访问堆顶元素（队头元素） |
| size | 获取队列中有效元素个数 |
| empty | 判断队列是否为空 |
| swap | 交换两个队列的元素 |
priority_queue的模拟实现
模拟实现：
//仿函数/函数对象
//()运算符重载, 使用方式类似于函数调用，所以可以称为:仿函数
//建大堆
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
{//向上调整, 排大堆void AdjustUp(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_com(_con[child], _con[parent])) //使用所给比较方式进行比较{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整，排大堆void AdjustDown(size_t parent){compare con; size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _com(_con[child + 1], _con[child])){++child;}if (_com(_con[child], _con[parent])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}
public:priority_queue(){}template<class inputiterator>priority_queue(inputiterator first, inputiterator last){while (first != last){_con.push_back(*first);++first;}//大堆for (size_t end = (_con.size() - 2) / 2; end >= 0; ++end){AdjustDown(end);}}void push(const T& key){_con.push_back(key);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}T& top(){return _con.front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}
private:container _con;compare _com;
};
