时间戳

首页 > 技术文章 > priority_queue（优先队列）的用法（包括pbds）

priority_queue（优先队列）的用法（包括pbds）

battlin 2019-11-11 16:18 原文

置顶！！！

有时候在定义的时候，不要把两个<<或者>>连在一起写，以免被编译器错误理解！！！！

头文件

#include <queue>

queue的一般用法不再叙述

类型名 priority_queue

常用函数

（设变量名为q）

q.pop();
q.push(x);
q.size();
q.empty();
q.top();   //注意与一般的queue中的q.front()不同

一般默认大根堆

使用小根堆的方法

priority_queue<int,vector<int>,greater<int>> q; //当然大根堆就是less

自定义优先级：

方法一：

struct rec{
    int a,b
}；

struct cmp {     
    bool operator ()(rec x, rec y)     
    {        
        return x.a > y.a; //结构体中，x小的优先级高 （意即大于号出来的是小根堆）   
    }
};

priority_queue<int, vector<int>, cmp> q; //定义方法

方法二：

struct node {     
    int x, y;     
    friend bool operator < (node a, node b)     
    {         
        return a.x > b.x;    //结构体中，x小的优先级高 （意即大于号出来的是小根堆）    
    }
};

priority_queue<node>q; //定义方法

//通过自定义operator<操作符来比较元素中的优先级。

//在重载”<”时，最好不要重载”>”，可能会发生编译错误

下面是平板电视的部分

pb_ds头文件

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//这个是pb_ds要求的头文件，注意平板电视里面涉及的头文件都不在bits/std标准库中

优先队列（堆）要求的头文件

#include <ext/pb_ds/priority_queue.hpp>

命名空间

using namespace __gnu_pbds;
（当心前面是两个下划线啊，当心啊！！！）

//当然pb_ds还有其他非常好用的数据结构，只不过我现在还不会

//留个坑待填（虽然可能不会填）

常用函数

与priority_queue基本相同

有一些拓展的函数

q.join(q1);  //把q1全部合并到q中去，并且把q1清空

q.point_iterator; //对应某元素的迭代器
q.erase(point_iterator it);  //删除对应点
q.modify(point_iterator it,const_reference r_new_val); //修改对应点的值(这是优化dijkstra神方法,均摊复杂度O(1))
//迭代器这一部分我不会啊  又留了一个坑
//如果学会就好了，这个确实很实用

定义方法

__gnu_pbds::priority_queue<int,greater<int>,TAG> Q;//小根堆，大根堆写less<int>
//注意这个里面的前面的__gnu_pbds::不要省略，因为虽然定义了命名空间，但是因为标准库里面也有priority_queue,这个就很ambigious

其中的TAG为类型，有以下几种：

pairing_heap_tag
thin_heap_tag
binomial_heap_tag
rc_binomial_heap_tag 
binary_heap_tag
其中pairing_help_tag最快

关于自定义的比较

对于上方的两种方式，经过我的多次实验，发现只有第一个可用，第二种无论我怎么调都是CE，这个与优先队列的定义方法有关

就采用第一种罢！

对于第一种，结构体定义都是一样的

定义方法改成这样
__gnu_pbds::priority_queue<rec,cmp,pairing_heap_tag> Q;

大概就是以上部分

推荐阅读