C++深入刨析优先级队列priority_queue的使用

　　template

　　struct less

　　{

　　bool operator()(const T& x, const T& y) const

　　{

　　return x < y;

　　}

　　};

　　template

　　struct greater

　　{

　　bool operator()(const T& x, const T& y) const

　　{

　　return x > y;

　　}

　　};

　　// 优先级队列 -- 大堆 < 小堆 >

　　template, class Compare = less>

　　class priority_queue

　　{

　　public:

　　void AdjustUp(int child)

　　{

　　Compare comFunc;

　　int parent = (child - 1) / 2;

　　while (child > 0)

　　{

　　//if (_con[parent] < _con[child])

　　if (comFunc(_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);

　　}

　　void AdjustDown(int parent)

　　{

　　Compare comFunc;

　　size_t child = parent * 2 + 1;

　　while (child < _con.size())

　　{

　　//if (child+1 < _con.size() && _con[child] < _con[child+1])

　　if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))

　　{

　　++child;

　　}

　　//if (_con[parent] < _con[child])

　　if (comFunc(_con[parent], _con[child]))

　　{

　　swap(_con[parent], _con[child]);

　　parent = child;

　　child = parent * 2 + 1;

　　}

　　else

　　{

　　break;

　　}

　　}

　　}

　　void pop()

　　{

　　assert(!_con.empty());

　　swap(_con[0], _con[_con.size() - 1]);

　　_con.pop_back();

　　AdjustDown(0);

　　}

　　const T& top()

　　{

　　return _con[0];

　　}

　　size_t size()

　　{

　　return _con.size();

　　}

　　bool empty()

　　{

　　return _con.empty();

　　}

　　private:

　　Container _con;

　　};