posts - 0,  comments - 0,  trackbacks - 0
priority_queue & 结构体||类 & 自定义比较函数cmp （转载）

template< class T ,

                     class Sequence=vector<T> ,

                     class Compare=less<typename Sequence::value_type> >

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

struct node {
     int no;
     int year;
     int period;
     int current;
};
int num;

struct cmp {
     bool operator() (const node &a, const node &b)
     {
         if (a.current < b.current)
             return false;
         else if (a.current == b.current)
             return (a.year > b.year);
         else return true;
     }
};

priority_queue<node, vector<node>, cmp> p;
void slove()
{
     while (num--)
     {
         node e = p.top();
         p.pop();
         printf("%d\n", e.year);
         e.current += e.period;
         p.push(e);
     }
}

int main()
{
     node a;
     char s[100];

     for (int i=0; scanf("%s", s) && strcmp(s, "#"); i++)
     {
         scanf("%d%d", &a.year, &a.period);
         a.current = a.period;
         a.no = i;
         p.push(a);
     }
     scanf("%d", &num);
     slove();

     return 0;
}

copy to clipboard?
  1. #include<iostream>  
  2. #include<vector>  
  3. #include<queue>  
  4. using namespace std;  
  5. struct node  
  6. {  
  7.     int x;  
  8.     int y;  
  9.     int w;  
  10.     friend bool operator> (const node& a,const node& b)  
  11.     {  
  12.         return (a.w > b.w);  
  13.     }  
  14.     friend bool operator< (const node& a,const node& b)  
  15.     {  
  16.         return (a.w < b.w);  
  17.     }  
  18. };  
  19. int main()  
  20. {  
  21.     int i;  
  22.     priority_queue < node, vector<node>, greater<node> > que1;  
  23.     //priority_queue < node, vector<node>, greater<node>>(两个连在一起不行) que;  
  24.     priority_queue < node, vector<node>, less<node> > que2;  
  25.     node da[5];  
  26.     for(i = 0;i < 5;i++)   
  27.     {  
  28.         da[i].x = i;  
  29.         da[i].y = i;  
  30.         da[i].w = i;  
  31.         que1.push(da[i]);  
  32.         que2.push(da[i]);  
  33.     }  
  34.     while(!que1.empty())  
  35.     {  
  36.         cout<<que1.top().x<<" "<<que1.top().y<<" "<<que1.top().w<<endl;  
  37.         que1.pop();  
  38.     }  
  39.     cout<<endl;  
  40.     while(!que2.empty())  
  41.     {  
  42.         cout<<que2.top().x<<" "<<que2.top().y<<" "<<que2.top().w<<endl;  
  43.         que2.pop();  
  44.     }  
  45.     cout<<endl;  
  46.     return 0;  
  47. }  
 

 

copy to clipboard?
  1. #include<iostream>  
  2. #include<vector>  
  3. #include<queue>  
  4. using namespace std;  
  5. struct node  
  6. {  
  7.     int x;  
  8.     int y;  
  9.     int w;  
  10. };  
  11. struct node_greater_cmp  
  12. {  
  13.     bool operator()(const node& a,const node& b)  
  14.     {  
  15.         return a.w > b.w;  
  16.     }  
  17. };  
  18. struct node_less_cmp  
  19. {  
  20.     bool operator()(const node& a,const node& b)  
  21.     {  
  22.         return a.w < b.w;  
  23.     }  
  24. };  
  25.   
  26. int main()  
  27. {  
  28.     int i;  
  29.     priority_queue < node, vector<node>, node_greater_cmp > que1;  
  30.     priority_queue < node, vector<node>, node_less_cmp > que2;  
  31.     node da[5];  
  32.     for(i = 0;i < 5;i++)   
  33.     {  
  34.         da[i].x = i;  
  35.         da[i].y = i;  
  36.         da[i].w = i;  
  37.         que1.push(da[i]);  
  38.         que2.push(da[i]);  
  39.     }  
  40.     while(!que1.empty())  
  41.     {  
  42.         cout<<que1.top().x<<" "<<que1.top().y<<" "<<que1.top().w<<endl;  
  43.         que1.pop();  
  44.     }  
  45.     cout<<endl;  
  46.     while(!que2.empty())  
  47.     {  
  48.         cout<<que2.top().x<<" "<<que2.top().y<<" "<<que2.top().w<<endl;  
  49.         que2.pop();  
  50.     }  
  51.     cout<<endl;  
  52.     return 0;  
  53. }  
 

 

copy to clipboard?
  1. class   Enity     
  2.   {     
  3.   public:     
  4.   int   mId;     
  5.   std::string   mName;     
  6.   };     
  7.       
  8.   class   Lesser     
  9.   {     
  10.   public:     
  11.   bool   operator   ()   (Enity   a,   Enity   b)     
  12.   {     
  13.   return   a.mId   >   b.mId;     
  14.   }     
  15.   };     
  16.       
  17.   int   _tmain(int   argc,   _TCHAR*   argv[])     
  18.   {     
  19.   priority_queue<Enity,   vector<Enity>,   Lesser>   q;     
  20.       
  21.   Enity   a,   b,   c;     
  22.   a.mId   =   2;     
  23.   b.mId   =   1;     
  24.   c.mId   =   3;     
  25.       
  26.   q.push(a);     
  27.   q.push(b);     
  28.   q.push(c);     
  29.       
  30.   cout   <<   q.top().mId   <<   endl;     
  31.   q.pop();     
  32.   cout   <<   q.top().mId   <<   endl;     
  33.   q.pop();     
  34.   cout   <<   q.top().mId   <<   endl;     
  35.   q.pop();     
  36.       
  37.   return   0;     
  38.   }  
 

 

priority_queue用法详解v2

2009年7月3日creke发表评论阅读评论

大部分内容来自某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是一样的。
posted on 2011-02-13 16:45 avcpp 阅读(1262) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2026年6月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿

文章档案

搜索

  •  

最新评论