codeofthrone's blog

By codeofthrone, history, 2 months ago, In English,

Is it possible to to have a custom comparator function for priority queue which keeps on changing. If not is their any way to implement this functionality. Ex:

#define fi first
#define se second

int X,Y;
struct comp
{
    bool operator()(pair<int,int>& A, pair<int,int> & B)
    {
        int x1=A.fi,y1=A.se,x2=B.fi,y2=B.se;
        if((abs(X-x1)+abs(Y-y1))>(abs(X-x2)+abs(Y-y2)))
        {
            return false;
        }
        else
        return true;
    }
    
};

////in MAin

 X=1,Y=1;
   priority_queue<pair<int,int>, vector<pair<int,int>  >,comp>PQ;
   for(int i=1;i<=N;i++)
   {
       for(int j=1;j<=M;j++)
       {
           if(i==1 && j==1) continue;
           PQ.push(m_p(i,j));
       }
   }
   cout<<1<<" "<<1<<endl;
   while(!PQ.empty())
   {
       int x=PQ.top().fi;
       int y=PQ.top().se;
       cout<<x<<" "<<y<<endl;
       PQ.pop();
       X=x;Y=y;
   }

as we keep on changing X,Y, our PQ will change itself accordingly?

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

priority_queue does not work like this, but you can implement the functionality based on set and/or multiset.

The update operation is an erase followed by an insert.

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In fact you need to keep the function's result stable all time , or STL will give you an unpredicted error.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by codeofthrone (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

priority_queue provides constant lookup for the highest priority element and logarithmic time for insertion. To guarantee those time complexities, it maintains a data structure (usually binary heap) with all the elements in some order. You can see, how by definition it's not possible to do what you are asking. As whenever you change the comparator function, the already maintained order of elements is not useful anymore. So after changing the comparator, it's the same as finding the highest value from some new set of elements.