C++ 优先队列

优先队列工作原理: 自动排序的队列
1 . 出队:弹出最小(大)。

2.  入队:插入一个元素,并调整好顺序。

而优先队列排序有什么优势呢?如图可知。

声明一个优先队列,先调用#include<queue>

priority_queue <int> q;        //大根堆,从大到小排序

priority_queue <int,vector<int>,greater<int>/*注意这里必须有空格*/  > q;     //小根堆,从小到大排序

5个基本操作:

q.empty()     判空: 如果队列为空,则返回真
q.pop()    弹栈: 删除对顶元素,删除第一个元素
q.push()       压栈: 加入一个元素
q.size()      尺寸: 返回优先队列中拥有的元素个数
q.top()     栈顶元素:返回优先队列队顶元素,返回优先队列中有最高优先级的元素

入门优先队列问题

#include<queue>
#include<cstdio>
using namespace std;
priority_queue <int ,vector<int>,greater<int> > q;//小根堆
int n,a,ans;
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++)
  {
      scanf("%d",&a);
      q.push(a);
  }
  for (int i=1;i<=n-1;i++)
  {
      int q1=q.top();
      q.pop();
      int q2=q.top();
      q.pop();
      ans+=q1+q2;
      q.push(q1+q2);
  }
  printf("%d",ans);
 return 0;    
}

 看吧,就是一个简单贪心。

在拓展一点关于重定义的知识:

若入队的是一个结构体,怎样实现按关键字优先

大根堆示例:

priority_queue<int> q;
struct edge{
    int t,v;
    friend bool operator < (edge a,edge b)  //大根堆重载小于符号 
    {
        return a.t<b.t;         //注意是小于,大于就是小跟堆了  
    }
}e[1005];

小根堆示例:

priority_queue<int,vector<int>,greater<int> > q;
struct edge{
    int t,v;
    friend bool operator > (edge a,edge b)  //小根堆重载大于符号 
    {
        return a.t>b.t;         //注意是大于
    }
}e[1005];

所以优先队列是一种很简单的数据结构,多练就会了!~~orz

奶牛晒衣服

钓鱼

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/mzyczly/p/10767872.html