priority_queue--优先队列

一、认识优先队列

        priority_queue（优先队列）是 C++ 标准模板库（STL）中的一个容器适配器。它的底层实现通常是用堆（一般是二叉堆）来实现的。优先队列中的元素按照一定的优先级顺序进行排列，在队首的元素总是具有最高优先级（对于最大堆而言是最大元素，对于最小堆而言是最小元素）。

        它就像是一个特殊的队列，普通队列是先进先出（FIFO），而优先队列是按照优先级高低来决定出队的顺序。

二、优先队列的模拟实现

#include<iostream>
#include<vector>
#include<deque>using namespace std;
namespace ts
{template<class T, class Container = vector<int>, class Compare = less<T> >class priority_queue{public://向上调整建堆法void AdiustUp(int child){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 AdiustDown(int parent){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;}}}priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);AdiustUp(_con.size() - 1);++first;}}void push(const T& x){_con.push_back(x);AdiustUp(_con.size() - 1);}bool empty()const{return _con.empty();}const T& top()const{return _con.front();}const size_t size()const{return _con.size();}void pop(){swap(_con[0],_con[_con.size() - 1]);_con.pop_back();AdiustDown(0);}private:Container _con;Compare _com;};
}