STL 之 priority_queue 优先级队列

ACM算法日常

发布于 2019-03-18 11:09:54

9160

发布于 2019-03-18 11:09:54

文章被收录于专栏：ACM算法日常

priority_queue 优先级队列,鄙人以为这是一种很重要的迭代器，重要到是图论位必备技能。

掌握好priority_queue是为了后期学Dijkstra和SPFA等图论算法的基础。

priority_queue 介绍

priority_queue 优先队列的核心操作是支持在常量时间内获得最优先的元素。priority_queue 的难点就在于如何构造优先队列，更具体的说是如何使用自己定义的结构作为优先队列中的元素。

priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数，priority_queue<Type, Container, Functional>

Type 为数据类型

Container 为保存数据的容器

Functional 为元素比较方式。

Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list。STL里面容器默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。

priority_queue 功能函数

创建 priority_queue

priority_queue ()

例如：priority_queue<int> pq;

prioriy_queue (const priority_queue &)

例如：priority_queue<int> pq2(pq);

元素入队

void push(const value_type &x)

元素出队

void pop()

取队首元素

const value_type& top() const

队列非空判断

bool empty()

队列中元素个数

size_type size() // size_type为一个无符号整数

总的来说以下各种重载就是，重载一下小于号的操作而已！！

就像：priority_queue<Node,vector<Node>,cmp> q;

构建优先队列

例一：构建一个 int 型大顶堆，队头元素最大 (如果需要一个小顶堆，将仿函数 less 修改为 greater)

#include <iostream>
#include <queue>
using namespace std;
int main(){
    priority_queue<int,vector<int>,less<int> > q1;//使用priority_queue<int> q1;一样
    for(int i=0;i<10;i++)
        q1.push(i);
    while(!q1.empty()){
        cout<<q1.top()<< endl;
        q1.pop();
    }
    return 0;
}

例二：自定义数据类型的优先队列

对于自定义类型，则必须自己重载 operator< 或者自己写仿函数:

(1) 自定义类型重载 operator<

重载 operator< 后，声明对象时就可以只带一个模板参数。此时不能像基本类型这样声明 priority_queue<Node, vector<Node>, greater<Node> >。例如建立一个分别按照 x, y 值的升序优先队列

结构体外的重载

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int x, y;
}node;
 bool operator<(const Node & a, const Node & b){
    if(a.x==b.x) return a.y>b.y;
    return a.x>b.x;
}
 int main(){
    priority_queue<Node>q;
    for(int i=0;i<10;i++){
        node.x=i;
        node.y=10-i/3;
        q.push(node);
    }
    while(!q.empty()){
        cout<<q.top().x <<' '<<q.top().y<<endl;
        q.pop();
    }
    return 0;
}

结构体内的重载

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int x, y;
    bool operator < (const Node &b)const{
        if(x==b.x) return y>b.y;
        return x>b.x;
    }
}node;


 int main(){
    priority_queue<Node> q;
    for(int i=0;i<10;i++){
        node.x=i;
        node.y=10-i/3;
        q.push(node);
    }
    while(!q.empty()){
        cout<<q.top().x<<' '<<q.top().y<<endl;
        q.pop();
    }
    return 0;
}

(2) 自己写仿函数

实现带仿函数的声明，如：priority_queue<Node, vector<Node>, greater<Node> >

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int x, y;
}node;
struct cmp{
    bool operator()(const Node & a,const Node & b){
        if(a.x==b.x) return a.y>b.y;
        return a.x>b.x;}
};

 int main(){
    priority_queue<Node,vector<Node>,cmp> q;
    for(int i=0;i<10;i++){
        node.x=i;
        node.y=10-i/3;
        q.push(node);
    }
    while(!q.empty()){
        cout<<q.top().x<<' '<<q.top().y<<endl;
        q.pop();
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-03-04，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js