学校网站建设报价,wordpress仿简书主题,网页设计制作课程设计报告,新冠疫苗最新官方消息目录
priority_queue定义
prority_queue容器内元素的访问
priority_queue()常用函数实例解析
priority_queue内元素优先级的设置
priority_queue的常见用途 priority_queue又称为优先队列#xff0c;其底层是用堆来进行实现的。在优先队列中#xff0c;队首元素一定是当…目录
priority_queue定义
prority_queue容器内元素的访问
priority_queue()常用函数实例解析
priority_queue内元素优先级的设置
priority_queue的常见用途 priority_queue又称为优先队列其底层是用堆来进行实现的。在优先队列中队首元素一定是当前队列中优先级最高的那一个。例如在队列有如下元素且定义好了优先级
桃子优先级3
梨子优先级4
苹果优先级1
那么出队的顺序为梨子4、桃子3、苹果1
当然可以在任何时候往优先队列里面加入元素而优先队列底层的数据结构堆会随时调整结构使得每次的队首元素都是优先级最大的。关于这里的优先级则是规定出来的。
priority_queue定义
其定义的写法和其他STL容器相同typename可以是任意基本数据类型或容器
prioroty_queuetypename name;
prority_queue容器内元素的访问
和队列不一样的是优先队列没有front()函数与back()函数而只能通过top()函数来访问队首元素也就是优先级最高的元素。
#includestdio.h
#includequeue
using namespace std;
int main(){priority_queueint q;q.push(3);q.push(4);q.push(1);printf(%d\n,q.top());return 0;
}
输出结果
4
priority_queue()常用函数实例解析
1push()
push(x)将令x入队时间复杂度为其中N为当前优先队列中的元素个数
2top()
top()可以获得队首元素时间复杂度为
3pop()
pop()令队首元素出队时间复杂度为其中N为当前优先队列中的元素个数。
#includestdio.h
#includequeue
using namespace std;
int main(){priority_queueint q;q.push(3);q.push(4);q.push(1);printf(%d\n,q.top());q.pop();printf(%d\n,q.top());return 0;
}
输出结果
4
3
4empty()
empty()检测优先队列是否为空返回true则空返回false则非空时间复杂度为
#includestdio.h
#includequeue
using namespace std;
int main(){priority_queueint q;if(q.empty()true){printf(Empty\n);}else{printf(Not Empty\n);}q.push(1);if(q.empty()true){printf(Empty\n);}else{printf(Not Empty\n);}return 0;
}
5size()
size()返回优先队列内元素的个数时间复杂度为
#includestdio.h
#includequeue
using namespace std;
int main(){priority_queueint q;q.push(3);q.push(4);q.push(1);printf(%d\n,q.size());return 0;
}
priority_queue内元素优先级的设置
如何定义优先队列内元素的优先级是运用好优先队列的关键下面分别介绍基本数据类型与结构体类型的优先级设置方法。
1基本数据类型的优先级设置
此处指的基本数据类型就是int型double型char型等可以直接使用的数据类型优先队列对它们的优先级设置一般是数字大的优先级越高因此队首元素就是优先队列内的元素最大的那个如果char型则是字典序最大的。对基本数据类型来说下面两种优先队列的定义是等价的以int型为例
prioroty_queueint q;
priority_queueint,vectorint,lessint q;
可以发现第二种定义方式的尖括号多出了两个参数一个是vectorint另一个是lessint。其中vectorint填写的是来承载底层数据结构堆的容器如果第一个参数是double型或char型则此处只需要填写vectordouble或vectorchar而第三个参数lessint则是对第一个参数的比较类lessint表示数字大的优先级越大而greaterint表示数字小的优先级越大。
因此如果想让优先队列总是把最小的元素放在队首只需进行如下定义
priority_queueint,vectorint,greaterint q;
#includestdio.h
#includequeue
using namespace std;
int main(){priority_queueint,vectorint,greaterint q;q.push(3);q.push(4);q.push(1);printf(%d\n,q.top());return 0;
}
输出结果
1
事实上即便是基本数据类型也可以使用下面的结构体的优先级设置方法只不过第三个参数的写法不太一样。
2结构体的优先级设置
可以举一个水果的例子对水果的价格和名称建立一个结构体
struct fruit{string name;int price;
};
现在希望按水果的价格高的为优先级高就需要重载小于号。重载是指对已有的运算符进行重新定义也就是说可以改变小于号的功能写法如下
struct fruit{string name;int price;friend bool operator (fruit f1,fruit f2){return f1.price f2.price;}
};
可以看到fruit结构体增加了一个函数其中”friend为友元后面的”bool operator (fruit f1,fruit f2)对fruit类型的操作符“进行了重载重载大于号会编译错误因为从数学上来说只需要重载小于号即f1f2等价于判断f2f1而f1f2等价于判断!(f1f2)!(f2f1)函数内部为return f1.pricef2.price因此重载后小于号还是小于号的作用。此时就可以直接定义fruit类型的优先队列其内部就是以价格高的水果为优先级高。
priority_queuefruit q;
同理如果想要以价格低的水果为优先级高那么只需要把return中的小于号改为大于号即可。
struct fruit{string name;int price;friend bool operator (fruit f1,fruit f2){return f1.price f2.price;}
};
完整代码如下
#includeiostream
#includestring
#includequeue
using namespace std;
struct fruit{string name;int price;friend bool operator (fruit f1,fruit f2){return f1.price f2.price;}
}f1,f2,f3;
int main(){priority_queuefruit q;f1.name桃子;f1.price3;f2.name梨子;f2.price4;f3.name苹果;f3.price1;q.push(f1);q.push(f2);q.push(f3);coutq.top().name q.top().priceendl;return 0;
}
输出结果
苹果 1
此处对小于号的重载与排序函数sort中的cmp函数有些相似它们的参数都是两个变量函数内部都是return了true或者false。事实上这两者的作用确实是类似的只不过效果看上去似乎是相反的。在排序中如果return f1.pricef2.price那么则是按照价格从高到低排序但是在优先队列中却是把价格低的放在队首。原因在于优先队列本身静默的规则就是优先级高的放在队首因此把小于号重载为大于号的功能时只是把这个规则反向了一下。只需要记住优先队列的这个函数与sort中的cmp函数的效果是相反的。
或者也可以把结构体定义在外面只需要把friend去掉把小于号改成一对小括号然后把重载的函数写在结构体外面同时将其用struct包装起来。
struct cmp{bool operator () (fruit f1,fruit f2){return f1.price f2.price;}
};
在这种情况下需要用之前讲解的第二种定义方式来定义优先队列
priority_queuefruit,vectorfruit,cmp q;
完整代码如下
#includeiostream
#includestring
#includequeue
using namespace std;
struct fruit{string name;int price;
}f1,f2,f3;
struct cmp{bool operator () (fruit f1,fruit f2){return f1.price f2.price;}
};
int main(){priority_queuefruit,vectorfruit,cmp q;f1.name桃子;f1.price3;f2.name梨子;f2.price4;f3.name苹果;f3.price1;q.push(f1);q.push(f2);q.push(f3);coutq.top().name q.top().priceendl;return 0;
}
当然即便是基本数据类型或者其他STL容器也可以通过同样的方式来定义优先级。
最后指出如果结构体内的数据较为庞大例如出现了字符串或者数组建议使用引用来提高效率此时比较类的参数需要加上const和
friend bool operator (const fruit f1,const fruit f2){return f1.price f2.price;
}
bool operator() (const fruit f1,const fruit f2){return f1.price f2.price;
}
priority_queue的常见用途
priority_queue可以解决一些贪心问题也可以对Dijkstra算法进行优化。
但是注意在使用tiop()函数前必须用empty()判断优先队列是否为空。
