priority_queue & 结构体||类 & 自定义比较函数cmp

绝地灬酷狼 2022-05-25 10:51 44阅读 0赞

[http://blog.csdn.net/hongxdong/article/details/5559046][http_blog.csdn.net_hongxdong_article_details_5559046]

大部分内容来自某STL语法详解文档，贴出来应该没问题吧~~

1.先给一个简单应用的例子，这个和容器的用法差不多。

#include <iostream>
    #include <queue>
    using namespace std; 
    
    int main()
    {
        priority_queue<float> q;    //默认的是大顶堆 
    
        // insert three elements into the priority queue
        q.push(66.6);
        q.push(22.2);
        q.push(44.4); 
    
        // read and print two elements
        cout << q.top() << ' ';         //queue当中是q.front();
        q.pop();
        cout << q.top() << endl;
        q.pop(); 
    
        // insert three more elements
        q.push(11.1);
        q.push(55.5);
        q.push(33.3); 
    
        // skip one element
        q.pop(); 
    
        // pop and print remaining elements
        while (!q.empty())
        {
            cout << q.top() << ' ';
            q.pop();
        }
        cout << endl;
    }

2.下面是将节点存在优先队列中的两种方式

**最好**的方式：**这个简洁！**

struct Node
    {
        int x,y;
        bool operator <(Node a) const  {  return y < a.y; }
        bool operator >(Node a) const  {  return y > a.y; }
    };
        priority_queue<Node> A;                    //大根堆
        priority_queue<Node, vector<Node>, greater<Node> > B;    //小根堆

方式一：

struct Node
    {int adj;
     int val;
     friend  bool operator<(const Node &a,const Node &b) { return  a.val > b.val; }
    };
    priority_queue<Node>Q;

方式二：（cmp将结构体以val由大到小排列，组成大根堆）**一般也用这个！**

struct Node
    {int adj;
     int val;
    };
    struct cmp
    {bool operator()(Node a,Node b) { return  a.val > b.val; }
    };
    priority_queue<Node,vector<Node>,cmp>Q;

方式三：

struct TMax
    {
        TMax(int tx):x(tx){}
        int x;
    }; 
    
    struct TMin
    {
        TMin(int tx):x(tx){}
        int x;
    }; 
    
    bool operator<(const TMax &a, const TMax &b)
    {
        return a.x<b.x;
    } 
    
    bool operator<(const TMin &a, const TMin &b)
    {
        return a.x>b.x;
    } 
    
    priority_queue<TMax> hmax;    //大顶堆
    priority_queue<TMin> hmin;    //小顶堆

3.下面是将指针存在优先队列中的方式

struct Node
    {
         short f;
         short d;
         short fishs;
         short times;
         short i;
    }; 
    
    struct PCmp
    {
        bool operator () (Node const *x, Node const *y)
        {
            if(x->f == y->f)
                return x->i > y->i;
            return x->f < y->f;
        }
    }; 
    
    priority_queue<Node*, vector<Node*>, PCmp > Q;

注：在这种情况下往往可以预分配空间以避免new带来的麻烦。例如：堆中定义Node Qt\[26\]， 栈中的使用则为Node \*tmp1 = Qt。

经过测试，在优选队列当中存指针进行一系列操作要比存节点进行一系列操作快一些。

**注：**

1.  less<class T>这是大顶堆，按值大的优先，值大的在最上面。greater<class T>这是小顶堆，按值小的优先，值小的在最上面。
2.  自定义cmp如果还有不明白的看这里：
    
        struct cmp
        {
         bool operator()（const int &a,const int &b）//这里的&是引用
         {
          return a>b;//最大堆
          return a<b;//最小堆
         }
        };
        priority_queue< int, vector<int>, cmp >
3.  还是自定义cmp函数，注意，一般ACM中用结构体内含“bool operator()（const int &a,const int &b）”。这其实等价于Class cmp，不过更省事，当然也不规范（不需要规范）。
4.  return就是希望如何排列为true。如果希望由大到小，就将大到小的情况return；反则亦然。和sort的自定义cmp是一样的。

[http_blog.csdn.net_hongxdong_article_details_5559046]: http://blog.csdn.net/hongxdong/article/details/5559046