STL - priority_queue(优先队列）

参考：http://www.cnblogs.com/xzxl/p/7266404.html

一、基本定义：

优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序，可以重载“<”操作符来重新定义比较规则。

优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue，因为list的迭代器不是任意存取iterator，而pop中用到堆排序时是要求randomaccess iterator 的!)：
priority_queue<vector<int>, less<int> > pq1; 　　　 // 使用递增less<int>函数对象排序
priority_queue<deque<int>, greater<int> > pq2; 　　// 使用递减greater<int>函数对象排序
其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。

二、用途
最短路算法优化, 斜率DP优化等

三、代码实现&基本操作

///优先队列的基本使用

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

///自定义优先级方法1，定义结构，使用运算符重载

struct cmp1

{

    bool operator ()(int &a, int &b)

    {

        return a > b; //最小值优先（是“>" 注意别与排序搞混）

    }

};

struct cmp2

{

    bool operator ()(int &a, int &b)

    {

        return a < b; //最大值优先

    }

};

///自定义优先级方法2，定义结构，使用运算符重载

struct numb_1

{

    int x;

    bool operator < (const numb_1 &a) const {

        return x > a.x; //最小值优先（与前面的联系记忆）

    }

};

struct numb_2

{

    int x;

    bool operator < (const numb_2 &a) const {

        return x < a.x; //最大值优先

    }

};

///测试用数据

int a[] = {, , , , , , , };

numb_1 num1[] = {, , , , , , , }; //用于自定义方法2

numb_2 num2[] = {, , , , , , , }; //用于自定义方法2

int main()

{

    ///采用默认优先级

    priority_queue<int> que; //（由大到小）构造队列（最单纯的优先队列）

    ///自定义优先级方法1

    priority_queue<int, vector<int>,cmp1> que1; //最小值优先

    priority_queue<int, vector<int>,cmp2> que2; //最大值优先

    ///使用系统的函数

    //（注意最后的括号，不是“<<”, 因为”<<“是右移运算符

    priority_queue<int, vector<int>, greater<int> > que3; //最小值优先

    priority_queue<int, vector<int>, less<int> > que4; //最大值优先

    ///自定义优先级方法2

    priority_queue<numb_1> que5; //最小值优先

    priority_queue<numb_2> que6; //最大值优先

    ///Let's begin

    ///入队操作

    for(int i = ; a[i]; i++)

    {

        que.push(a[i]);

        que1.push(a[i]);

        que2.push(a[i]);

        que3.push(a[i]);

        que4.push(a[i]);

    }

    for(int i = ; num1[i].x; i++)

        que5.push(num1[i]);

    for(int i = ; num2[i].x; i++)

        que6.push(num2[i]);

    ///输出结果

    printf("采用默认优先级：\n");

    printf("（priority_queue<int>que;）\n");

    printf("Que 0:\n");

    while(!que.empty()) //判断是否为空

    {

        printf("%d ", que.top()); //队首元素

        que.pop(); //出队

    }

    puts("");

    puts("");

    printf("采用结构体自定义优先级方式一:\n");

    printf("(priority_queue<int,vector<int>,cmp>que;)\n");

    printf("Que 1:\n");

    while(!que1.empty()){

        printf("%d ",que1.top());

        que1.pop();

    }

    puts("");

    printf("Que 2:\n");

    while(!que2.empty()){

        printf("%d ",que2.top());

        que2.pop();

    }

    puts("");

    puts("");

    printf("采用头文件\"functional\"内定义优先级:\n");

    printf("(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n");

    printf("Que 3:\n");

    while(!que3.empty()){

        printf("%d ",que3.top());

        que3.pop();

    }

    puts("");

    printf("Que 4:\n");

    while(!que4.empty()){

        printf("%d ",que4.top());

        que4.pop();

    }

    puts("");

    puts("");

    printf("采用结构体自定义优先级方式二:\n");

    printf("(priority_queue<number>que)\n");

    printf("Que 5:\n");

    while(!que5.empty()){

        printf("%d ",que5.top());

        que5.pop();

    }

    puts("");

    printf("Que 6:\n");

    while(!que6.empty()){

        printf("%d ",que6.top());

        que6.pop();

    }

    puts("");

    return ;

}

巴特西

STL - priority_queue(优先队列）

最新文章

热门文章