免费网站建设有哪些,高端定制网站设计,海口有哪几家是做网站的,广东建设工程注册中心网站优先队列(priority queue)普通的队列是一种先进先出的数据结构#xff0c;元素在队列尾追加#xff0c;而从队列头删除。在优先队列中#xff0c;元素被赋予优先级。当访问元素时#xff0c;具有最高优先级的元素最先删除。优先队列具有最高级先出 #xff08;first in, l…优先队列(priority queue)普通的队列是一种先进先出的数据结构元素在队列尾追加而从队列头删除。在优先队列中元素被赋予优先级。当访问元素时具有最高优先级的元素最先删除。优先队列具有最高级先出 first in, largest out的行为特征。优先队列是队列的一种不过它可以按照自定义的一种方式数据的优先级来对队列中的数据进行动态的排序 每次的push和pop操作队列都会动态的调整以达到我们预期的方式来存储。 例如我们常用的操作就是对数据排序优先队列默认的是数据大的优先级高 所以我们无论按照什么顺序push一堆数最终在队列里总是top出最大的元素。 优先队列的常用操作 优先级队列支持的操作 q.empty() 如果队列为空则返回true否则返回false q.size() 返回队列中元素的个数 q.pop() 删除队首元素但不返回其值 q.top() 返回具有最高优先级的元素值但不删除该元素 q.push(item) 在基于优先级的适当位置插入新元素 用法 示例将元素53246依次push到优先队列中print其输出。 1. 标准库默认使用元素类型的操作符来确定它们之间的优先级关系。 priority_queueint pq; 通过操作符可知在整数中元素大的优先级高。 故示例1中输出结果为 6 5 4 3 2 2. 数据越小优先级越高 priority_queueint, vectorint, greaterint pq; 其中 第二个参数为容器类型。 第二个参数为比较函数。 故示例2中输出结果为2 3 4 5 6 3. 自定义优先级重载比较符号 重载默认的 符号 struct node
{friend bool operator (node n1, node n2){return n1.priority n2.priority;}int priority;int value;
}; 这时需要为每个元素自定义一个优先级。 注重载号会编译出错因为标准库默认使用元素类型的操作符来确定它们之间的优先级关系。 而且自定义类型的操作符与操作符并无直接联系 #includeiostream
#includefunctional
#includequeue
using Namespace stdnamespace std;
struct node
{friend bool operator (node n1, node n2){return n1.priority n2.priority;}int priority;int value;
};
int main()
{const int len 5;int i;int a[len] {3,5,9,6,2};//示例1priority_queueint qi;for(i 0; i len; i)qi.push(a[i]);for(i 0; i len; i){coutqi.top() ;qi.pop();}coutendl;//示例2priority_queueint, vectorint, greaterint qi2;for(i 0; i len; i)qi2.push(a[i]);for(i 0; i len; i){coutqi2.top() ;qi2.pop();}coutendl;//示例3priority_queuenode qn;node b[len];b[0].priority 6; b[0].value 1; b[1].priority 9; b[1].value 5; b[2].priority 2; b[2].value 3; b[3].priority 8; b[3].value 2; b[4].priority 1; b[4].value 4; for(i 0; i len; i)qn.push(b[i]);cout优先级\t值endl;for(i 0; i len; i){coutqn.top().priority\tqn.top().valueendl;qn.pop();}return 0;
} 先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container 不能用来实现queue因为list 的迭代器不是任意存取iterator而pop 中用到堆排序时是要求randomaccess iterator 的!) priority_queuevectorint, lessint pq1; // 使用递增lessint函数对象排序 priority_queuedequeint, greaterint pq2; // 使用递减greaterint函数对象排序 其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。 例 1 #include iostream 2 #include queue 3 using namespace std; 4 5 class T { 6 public: 7 int x, y, z; 8 T(int a, int b, int c):x(a), y(b), z(c) 9 { 10 } 11 }; 12 bool operator (const T t1, const T t2) 13 { 14 return t1.z t2.z; // 按照z的顺序来决定t1和t2的顺序 15 } 16 main() 17 { 18 priority_queueT q; 19 q.push(T(4,4,3)); 20 q.push(T(2,2,5)); 21 q.push(T(1,5,4)); 22 q.push(T(3,3,6)); 23 while (!q.empty()) 24 { 25 T t q.top(); 26 q.pop(); 27 cout t.x t.y t.z endl; 28 } 29 return 1; 30 } 输出结果为(注意是按照z的顺序从大到小出队的) 3 3 6 2 2 5 1 5 4 4 4 3 再看一个按照z的顺序从小到大出队的例子 1 #include iostream 2 #include queue 3 using namespace std; 4 class T 5 { 6 public: 7 int x, y, z; 8 T(int a, int b, int c):x(a), y(b), z(c) 9 { 10 } 11 }; 12 bool operator (const T t1, const T t2) 13 { 14 return t1.z t2.z; 15 } 16 main() 17 { 18 priority_queueT, vectorT, greaterT q; 19 q.push(T(4,4,3)); 20 q.push(T(2,2,5)); 21 q.push(T(1,5,4)); 22 q.push(T(3,3,6)); 23 while (!q.empty()) 24 { 25 T t q.top(); 26 q.pop(); 27 cout t.x t.y t.z endl; 28 } 29 return 1; 30 } 输出结果为 4 4 3 1 5 4 2 2 5 3 3 6 如果我们把第一个例子中的比较运算符重载为 bool operator (const T t1, const T t2) { return t1.z t2.z; // 按照z的顺序来决定t1和t2的顺序} 则第一个例子的程序会得到和第二个例子的程序相同的输出结果。
