首页 > 代码库 > c++ 优先级队列(priority_queue)

c++ 优先级队列(priority_queue)

2024-09-20 19:12:51   225人阅读

从网上搜优先级队列用法，都是有些乱七八糟的，有几种用法都没说，直接贴代码。实在郁闷，于是自己在此归纳归纳。

废话不多说，直入主题。

优先级队列的核心是比较函数的实现。

比较函数有两种实现方法：

1、在结构体或类外面定义一个比较结构体。  //假如有个Point结构体。则new对象的时候：priority_queue<Point,vector<Point>,cmp> pg;其中cmp是自定义比较函数

2、在结构体或类中自己重载<操作符。   //假如有个Point结构体。这种方式定义优先级队列: priority_queue<Point> pg;

 

 

第1种方法实现代码：

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

class Point
{
public:
    int x,y;
};

struct cmp
{
    bool operator()(Point a,Point b) 
    {
        return a.x>b.x;        //返回 !cmp 
    }
};

priority_queue<Point,vector<Point>,cmp> pq;
Point p;

int main()
{
    int n;
    while(cin>>n)
    {
        while(!pq.empty()) pq.pop();
        while(n--)
        {
            cin>>p.x>>p.y;
            pq.push(p);
        }
        while(!pq.empty())
        {
            cout<<pq.top().x<<"-"<<pq.top().y<<" ";
            pq.pop();
        }
    }
    return 0;
}

　　

第2种方法实现代码：

#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

class Point
{
public:
    friend bool operator <(Point a,Point b);
    int x,y;
};

//友元函数在外面实现 也可在类里面实现
bool operator <(Point a,Point b)      //优先级队列要求必须要实现<的重载，否则编译错误  而int型有默认的<函数。
{
    return a.x>b.x;         //返回比较结果的相反值，这种情况是从小到大排序
}

/** 友元函数在类里面实现如下
class Point
{
public:
    friend bool operator <(Point a,Point b)
    {
        return a.x>b.x;
    }
    int x,y;
};
**/
priority_queue<Point> pq;
Point p;

int main()
{
    int n;
    while(cin>>n)
    {
        while(!pq.empty()) pq.pop();
        while(n--)
        {
            cin>>p.x>>p.y;
            pq.push(p);
        }
        while(!pq.empty())
        {
            cout<<pq.top().x<<"-"<<pq.top().y<<" ";
            pq.pop();
        }
    }
    return 0;
}

　　

c++ 优先级队列(priority_queue)


联系
我们