婚介 东莞网站建设,wordpress对接steam,免费制作的企业网站,wordpress超简洁自适应html5博客主题:read使用
priority_queue
优先级队列与 stack 和 queue 一样#xff0c;也是一个容器适配器#xff0c;其底层通过 vector 来实现的。与 stack 和 queue 不同的是#xff0c;它的第一个元素总是它所包含的元素中最大或最小的一个。
也就是说#xff0c;优先级队列就是数据结…使用
priority_queue
优先级队列与 stack 和 queue 一样也是一个容器适配器其底层通过 vector 来实现的。与 stack 和 queue 不同的是它的第一个元素总是它所包含的元素中最大或最小的一个。
也就是说优先级队列就是数据结构中所说的堆。其通过堆的向上调整算法、向下调整算法等将其变为一个堆保证其第一个元素一定为其所包含元素中最大或最小的一个。 priority_queueint q;
q.push(9);
q.push(2);
q.push(7);
q.push(1);
q.push(5);while (!q.empty())
{cout q.top() ;q.pop();
}
cout endl;
模拟实现
基础实现
模拟实现优先级队列就是模拟实现堆要实现的核心接口为 push() 和 pop() 。(堆的实现详解)
其为适配器底层利用 vector 来实现。
默认实现为大堆。
#includevector//大堆
namespace Friend
{templateclass T, class Container vectorTclass priority_queue{public:bool empty() const{return con.empty();}size_t size() const{return con.size();}const T top() const{// 返回数组的第一个元素return con.front();}void AdjustUp(int child){int parent (child - 1) / 2;while (parent 0){if (con[parent] con[child]){std::swap(con[parent], con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){int child 2 * parent 1;while (child con.size()){if (child 1 con.size() con[child] con[child 1]){child;}if (con[parent] con[child]){std::swap(con[parent], con[child]);parent child;child 2 * parent 1;}else{break;}}}void push(const T x){// 在尾部插入一个新数据con.push_back(x);// 将其重新调整为堆AdjustUp(con.size() - 1);}// 删除堆顶的数据void pop(){// 交换堆顶和尾部的数据std::swap(con[0], con[con.size() - 1]);// 删除尾部数据con.pop_back();// 将其重新调整为堆AdjustDown(0);}private:Container con;};
}
仿函数
按照之前的方法如果要把大堆变为小堆就要把 AdjustUp( )、AdjustDown( ) 中所有的 ‘ 变为 ’ 十分麻烦。因此C 中使用仿函数来解决这个问题。
仿函数实际上为类并非真正的函数。
其通过重载了 ( ) 来控制大堆、小堆的变化。
templateclass T
class Less
{
public:// x -- i-1 ******* y -- ibool operator()(const T x, const T y){return x y;}
};templateclass T
class Greater
{
public:// x -- i-1 ******* y -- ibool operator()(const T x, const T y){return x y;}
};
由于其调用时像函数调用因此得名仿函数。
Lessint less;less(10, 20);
less.operator()(1, 9);Greaterint greater;greater(10, 20);
greater.operator()(1, 9);
改进
因此我们对代码进行改进。
namespace Friend
{templateclass T, class Container vectorT, class Compare LessTclass priority_queue{public:bool empty() const{return con.empty();}size_t size() const{return con.size();}const T top() const{// 返回数组的第一个元素return con.front();}void AdjustUp(int child){int parent (child - 1) / 2;while (parent 0){// if (con[parent] con[child])if (com(con[parent], con[child])){std::swap(con[parent], con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){int child 2 * parent 1;while (child con.size()){// if (child 1 con.size() con[child] con[child 1])if (child 1 con.size() com(con[child], con[child 1])){child;}// if (con[parent] con[child])if (com(con[parent], con[child])){std::swap(con[parent], con[child]);parent child;child 2 * parent 1;}else{break;}}}void push(const T x){// 在尾部插入一个新数据con.push_back(x);// 将其重新调整为堆AdjustUp(con.size() - 1);}// 删除堆顶的数据void pop(){// 交换堆顶和尾部的数据std::swap(con[0], con[con.size() - 1]);// 删除尾部数据con.pop_back();// 将其重新调整为堆AdjustDown(0);}private:Container con;Compare com;};
}
大堆时
Friend::priority_queueint q;
如果要变为小堆则
Friend::priority_queueint, vectorint, Greaterint q;
只需通过仿函数的变换就能达到目的。
