priority_queue

  priority_queue 优先队列,其底层是用堆来实现的。在优先队列中,队首元素一定是当前队列中优先级最高的那一个。

  在优先队列中,没有 front() 函数与 back() 函数,而只能通过 top() 函数来访问队首元素(也可称为堆顶元素),也就是优先级最高的元素。

一、基本数据类型的优先级设置

  1. 此处指的基本数据类型就是 int 型,double 型,char 型等可以直接使用的数据类型,优先队列对他们的优先级设置一般是数字大的优先级高,因此队首元素就是优先队列内元素最大的那个(如果是 char 型,则是字典序最大的)。

    //下面两种优先队列的定义是等价的
    priority_queue<int> q;
    priority_queue<int,vector<int>,less<int> >;//后面有一个空格

  
  • 1
  • 2
  • 3
  • 4
  • 5

  其中第二个参数( vector ),是来承载底层数据结构堆的容器,第三个参数( less ),则是一个比较类,less 表示数字大的优先级高,而 greater 表示数字小的优先级高

如果想让优先队列总是把最小的元素放在队首,只需进行如下的定义:


    priority_queue<int,vector<int>,greater<int> >q;

  
  • 1
  • 2
  • 3

示例代码:


    void test1(){
        //默认情况下,数值大的在队首位置(降序)
        priority_queue<int> q;
        for(int i  = 0;i <= 10;i ++)
            q.push(i);
        while(!q.empty()){
            cout<<q.top()<<" ";
            q.pop();
        }
        cout<<endl;

        //greater<int>表示数值小的优先级越大
        priority_queue<int,vector<int>,greater<int> > Q;
        for(int i  = 0;i <= 10;i ++)
            Q.push(i);
        while(!Q.empty()){
            cout<<Q.top()<<" ";
            Q.pop();
        }

    }

  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

二、结构体的优先级设置

1.方式一:重载运算符 ‘<’

  可以在结构体内部重载 ‘<’,改变小于号的功能(例如把他重载为大于号)


    struct student{
        int grade;
        string name;

        //重载运算符,grade 值高的优先级大
        friend operator < (student s1,student s2){
            return s1.grade < s2.grade;
        }
    };

  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

示例代码:


    void test2(){
        priority_queue<student> q;
        student s1,s2,s3;
        s1.grade = 90;
        s1.name = "Tom";

        s2.grade = 80;
        s2.name = "Jerry";

        s3.grade = 100;
        s3.name = "Kevin";

        q.push(s1);
        q.push(s2);
        q.push(s3);

        while(!q.empty()){
            cout<<q.top().name<<":"<<q.top().grade<<endl;
            q.pop();
        } 

    }
        /* 结果: Kevin:100 Tom:90 Jerry:80 */

  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

2.方式二:把重载的函数写在结构体外面

  将比较函数写在结构体外面,作为参数传给优先队列。


    struct fruit{
        string name;
        int price;
    };
    struct cmp{
        // "<" 表示 price 大的优先级高
        bool operator() (fruit f1,fruit f2){
            return f1.price < f2.price;
        }
    };

  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

示例代码:


    void test3(){
        priority_queue<fruit,vector<fruit>,cmp> q;
        fruit f1,f2,f3;

        f1.name = "apple";
        f1.price = 5;

        f2.name = "banana";
        f2.price = 6;

        f3.name = "pear";
        f3.price = 7;

        q.push(f1);
        q.push(f2);
        q.push(f3);

        while(!q.empty()){
            cout<<q.top().name<<":"<<q.top().price<<endl;
            q.pop();
        }
    }

    /* 结果: pear:7 banana:6 apple:5 */
  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30