网站做营销推广公司,漏惹网站做,设计和建设企业网站心得和体会,四川建设网站塔吊1. 什么是priority_queue
priority_queue是C中的容器#xff0c;实现优先队列。由于底层采用堆实现#xff0c;所以插入和删除操作的时间复杂度为O(logn)#xff0c;查找队首元素的时间复杂度为O(1)。
2. 构造priority_queue
【1】使用priority_queue需要先包含头文件中的容器实现优先队列。由于底层采用堆实现所以插入和删除操作的时间复杂度为O(logn)查找队首元素的时间复杂度为O(1)。
2. 构造priority_queue
【1】使用priority_queue需要先包含头文件queue。以下是priority_queue的基本语法
#include queue
priority_queueint pq;默认情况下priority_queue是一个大顶堆即队首元素是最大的元素由大到小排序。
【2】如果是自定义比较比如比较从小到大比较或不坏类中的某个元素则在声明priority_queue对象时需要指定元素类型和比较函数。
具体语法
// 声明一个元素类型为T比较函数为Compare的priority_queue对象
priority_queueT, vectorT, Compare pq;
其中T为元素类型std::vectorT为底层容器类型Compare为元素的比较函数是函数对象。
例如若要声明一个整型优先队列要求从小到大排序可以这样写
priority_queueint,vectorint,greaterint pq;
例如若要声明一个字符串优先队列要求按照字符串大小从小到大排序可以这样写
// 自定义比较函数
struct cmp {bool operator() (const std::string s1, const std::string s2) {return s1.size() s2.size(); // 按字符串长度从小到大排序}
};priority_queuestring, vectorstring, cmp pq;
【3】用已有的优先队列赋值
priority_queueint pq(vec.begin(), vec.end()); // 创建一个包含vec中所有元素的优先队列3. priority_queue的常用操作
3.1 插入元素
使用成员函数push()可以向priority_queue中插入一个元素插入后会自动按照优先级调整元素位置。
pq.push(10); // 向队列中插入元素10 pq.push(20); // 向队列中插入元素20
3.2 访问队首元素
使用成员函数top()可以访问priority_queue中的队首元素即最大小值。
int max_element pq.top(); // 获取大顶堆的队首元素即最大值
3.3 删除队首元素
使用成员函数pop()可以删除priority_queue中的队首元素即最大小值。
pq.pop(); // 删除大顶堆的队首元素即最大值
3.4 检查队列是否为空
使用成员函数empty()可以检查priority_queue是否为空。
if (pq.empty()) { // 队列为空
}
3.5 获取队列大小
使用成员函数size()可以获取priority_queue中元素的个数。
int count pq.size(); // 获取队列中元素的个数
