priority_queue优先队列

1.定义和初始化

• 初始化一个空的队列,按元素的值从大到小排列,值最大的在队首,名字为q(需要dataType是可以比较大小的,若为结构体需要重载比较运算符)

priority_queue<dataType>q;

• 初始化一个空的队列,按元素的值从小到大排列,值最小的在队首,名字为q

priority_queue<dataType,greater<>>q;

• 初始化一个数据类型为结构体(str)的优先队列

struct str { //重载小于号 这里的str实际上就是pair<int,int>
    int first;
    int second;
    bool operator <(const str& a) const{
        if (first == a.first)return second < a.second;
        else return first < a.first;
    }
};
//由于重载小于运算符时返回的是小于号,按普通排序应该小的排在前面,但优先队列(堆)是优先级大的在队首,故大的在前
priority_queue<str>q;

2.遍历

• priority_queue与queue一致,也不可以随机访问,故无法完整遍历之后还能保存元素

while(q.size()){
    cout<<q.top()<<endl;//队首元素访问变为top()
    q.pop();
}

3.内置方法

• push() 入队,将x加入队列中,置于队列最后

q.push(x);

• top() 访问并返回队列最前端元素

dataType res=q.top();

• pop() 出队,删除队首元素

q.pop();

4.提示

• 优先队列中的数据结构必须可以排序,不可以使用cmp比较函数,必须是在结构体中重写比较远算符
• 注意定义时候,若使用c/c++原有数据类型,写greater<>或less<>时不可以加(),与sort中不同,sort中要写为 greater<>()