天天看点

算法笔记6.6 priority_queue

priority_queue 优先队列,只可以访问队首元素top(),只可以pop()队首元素,可以随意push元素。会自动按照优先级排序。对于基本数据类型,按照数值由小到大(从队首到队尾排序)

1.基本方法

#include<iostream>
#include<queue>
using namespace std;

void empty(priority_queue<int> q){
  if(q.empty()){
    cout<<"空\n";
  }else{
    cout<<"非空\n";
  }
}

int main(){
  priority_queue<int> q;
  q.push(3);
  q.push(4);
  q.push(1);

  //4 3 2
  cout<<"队首:"<<q.top()<<endl;
  q.pop();//3 2
  cout<<"队首:"<<q.top()<<endl;

  cout<<"长度:"<<q.size()<<endl;
  q.pop();//2
  cout<<"长度:"<<q.size()<<endl;


  empty(q);
  q.pop();//null
  empty(q);

  return 0;
}      
算法笔记6.6 priority_queue

2.设置优先级别

(1)基本数据类型

这两种方式等价:(默认方式,less表示数字大的优先级大)
 priority_queue<int> q;
 priority_queue<int,vector<int>,less<int> > q;  //优先队列底层是堆,vector<int>就是承载底层的堆的 数字小的优先级大:
 priority_queue<int,vector<int>,greater<int> > q;      
#include<iostream>
#include<queue>
using namespace std;
int main(){
  priority_queue<int,vector<int>,greater<int> > q;
  q.push(3);
  q.push(4);
  q.push(1);
  cout<<q.top()<<endl;
  return 0;
}      
算法笔记6.6 priority_queue

3.结构体优先级设置(重载<运算符)

写法1:

#include<iostream>
#include<queue>
using namespace std;

struct fruit{
  string name;
  int price;

  fruit(string name,int price){
    this->name=name;
    this->price=price;
  }

  friend bool operator < (fruit f1,fruit f2){
    return f1.price<f2.price;//大的优先级高 和sort() cmp相反
  }

};

int main(){
  priority_queue<fruit> q;
  fruit f1=fruit("桃子",3);
  fruit f2=fruit("梨子",4);
  fruit f3=fruit("苹果",1);
  q.push(f1);
  q.push(f2);
  q.push(f3);
  cout<<q.top().name<<" "<<q.top().price<<endl;
  return 0;
}      
算法笔记6.6 priority_queue

写法2:

#include<iostream>
#include<queue>
using namespace std;

struct fruit{
  string name;
  int price;
  fruit(string name,int price){
    this->name=name;
    this->price=price;
  }

};

struct cmp{
  bool operator() (fruit f1,fruit f2){
    return f1.price>f2.price;//小的优先级别高 
  }
};

int main(){              //指定cmp结构体为比较依据
  priority_queue<fruit,vector<fruit>,cmp> q;
  fruit f1=fruit("桃子",3);
  fruit f2=fruit("梨子",4);
  fruit f3=fruit("苹果",1);
  q.push(f1);
  q.push(f2);
  q.push(f3);
  cout<<q.top().name<<" "<<q.top().price<<endl;
  return 0;
}      
算法笔记6.6 priority_queue

4.应用

贪心

dijkstra算法优化