C++ 优先队列 自定义优先规则

C++ 优先队列 自定义优先规则。
基础用法省略。

需要包含的头文件

#include <queue>

#include <functional>

不同的优先规则:针对基础数据类型。
默认大根堆
声明方法

priority_queue<int, vector<int>, greater<int> > q;  // 小根堆
priority_queue<int, vector<int>, less<int> > q;     // 大根堆

应用举例

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > p;
int main()
{
  int n=10;
  while(n--)
  {
    int temp;
    cin>>temp;
    p.push(temp);

  }
  while (!p.empty())
  {
    cout<<p.top()<<' ';
    p.pop();
  }

}

重载运算符实现自定义权重小根堆

方式一:

struct qnode
{
    int v;
    int c;
    qnode(int v=0,int c=0):v(v),c(c){}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
priority_queue<qnode>que;

完整应用代码:dijkstra模板题

方式二:

struct Node{
    int x, y;
    Node(int a = 0, int b= 0):x(a), y(b) {}
};
 
struct cmp{
    bool operator() (const Node& a, const Node& b ){
      if (a.x == b.x) 
      return a.y > b.y;
      return a.x > b.x; 
  }
};

priority_queue<Node, vector<Node>, cmp> q;

方式三:

struct Node{
    int x, y;
    Node(int a = 0, int b= 0):x(a), y(b) {}
};

bool operator < (const Node& a, const Node& b ){
    if (a.x == b.x) 
    return a.y > b.y;
    return a.x > b.x; 
}
 
priority_queue<Node> q;

 

发表评论

电子邮件地址不会被公开。