admin管理员组

文章数量:1623796

priority_queue(优先队列)，底层用堆实现的。队首元素是当前队列中优先级最高的一个，优先级是自己规定的。

使用：

  1. #include <queue>
  2. using namespace std;

1 priority_queue的定义

priority_queue<typename> name;

2 priority_queue容器内元素的访问

//top() 访问队首元素
q.top();

3 priority_queue常用函数实例解析

//1. push(x) x入队
q.push(3);

//2. top()

//3. pop() 队首元素出队
q.pop();

//4. empty() 检测是否为空，返回bool
q.empty();

//5. size() 返回个数
q.size();

4 priority_queue内元素优先级的设置

4.1 基本元素类型(int, double, char)的优先级设置

priority_queue<int> q;
priority_queue<int, vector<int>, less<int>> q;

上面两种定义等价。对于第2种定义：

  • vector<int>：表示用来承载底层数据结构堆(heap)的容器。前面是int，后面就是vector<int>
  • less<int>：表示数字大的优先级大；而greater<int>表示数字小的优先级越大。

4.2 结构体的优先级设置

其他基本数据类型或者其他STL容器(例如set)，也可以通过同样的方式来定义优先级。

//以水果为例子
struct fruit{
    string name;
    int price;
    //如果希望价格高为优先，需要重载"<"
    friend bool operator < (const fruit &f1,const fruit &f2){ //使用&引用提高效率
        return f1.price < f2.price; //如果是“>”，则表示价格低为优先
    }
};
priority_queue<fruit> q;
//--------------------------------------------------------或
struct cmp{
    bool operator () (const fruit &f1,const fruit &f2){
        return f1.price > f2.price; //sort与cmp符号相反，效果会相同
    }
};
priority_queue<fruit, vector<fruit>, cmp> q;

5 priority_queue的常见用途

  • 解决一些贪心问题，或者优化Dijkstra算法
  • 使用top()前，先empty()是否为空

本文标签： 函数常用stlPriorityQueue

版权声明：本文标题：【C++STL库】priority queue常用函数学习 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1728896141a1178433.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。