priority_queue使用方法

简单介绍一下:

priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数代价的插入与释出。可用用户提供的 Compare 更改顺序,例如,用 std::greater<T> 将导致最小元素作为 top() 出现。用 priority_queue 工作类似管理某些随机访问容器中的堆,优势是不可能突然把堆非法化。
模板申明带3个参数:priority_queue<Type, Container, Functional>,其中Type 为数据类型,Container为保存数据的容器,Functional 为元素比较方式。Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector。

比较方式默认用operator<,所以如果把后面2个参数缺省的话,优先队列就是大顶堆(降序),队头元素最大。
Priority_Queue 队列的头指排序规则最小那个元素。如果多个元素都是最小值则随机选一个。
如果要用到小顶堆,则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>,基本类型可以用这个仿函数声明小顶堆。 priority_queue<int, vector<int>, greater<int> > q;
对于自定义类型,则必须重载operator<或者重写仿函数。

using namespace std;
const int maxn=4e5+5;
struct node{
    int x,cnt;
    bool operator<(const node&t)const{     //return true说明x越小优先级越低,排在后面 
        return x<t.x;
    }
}a[maxn];

与普通队列的比较:
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。
在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。
头文件也是#include<queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。
优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的。
优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。该队列不允许使用 null 元素也不允许插入不可比较的对象(没有实现Comparable接口的对象)。

常用函数:

push()      //插入元素,并对底层容器排序,O(logn)
pop()       //删除栈顶元素,O(logn)
top()       //访问栈顶元素
size()      //返回容纳元素数
empty()     //检查底层的容器是否为空
Last modification:December 13th, 2019 at 01:17 am
如果觉得我的文章对你有用,请随意赞赏