codeofthrone's blog

dynamic comparative func for priority queue
By codeofthrone, history, 5 years 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

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No.

→ Reply
»
5 years 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.

→ Reply
»
5 years 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.

→ Reply
»
5 years 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.

→ Reply