Блог пользователя slow_hare

Автор slow_hare, история, 3 года назад, По-английски

I had a solution to a problem which included priority queue.

I wish to know if we can change the comparator of priority queue at run time like if we initially had the declaration as priority_queue<int> pq which will store no.s in non-increasing order, can I use the same priority queue to store no.s in increasing order after pq.clear()

Thanks

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

AFAIK there is no clear method for priority_queue in C++. What you can do is naively pop elements out or create a new priority_queue:

pq = priority_queue<int>();

Now comeback to your question, I haven't seen anyway to change the comparator. However there is a simple workaround using custom comparator.

int sign = -1;
bool cmp(const int &a, const int &b){
    return a * sign < b * sign;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    priority_queue<int, vector<int>, decltype(&cmp)> q(cmp);
    q.push(1); q.push(2); q.push(3);
    cout << q.top() << '\n';

    sign *= -1;
    q = priority_queue<int, vector<int>, decltype(&cmp)>(cmp);
    q.push(1); q.push(2); q.push(3);
    cout << q.top();
}

Output:

1
3

With sign equal to -1, small numbers will be prioritized and similar for sign equal to 1

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    does the comparator swaps element on the condition being true here?

    as with normal comparators with a = 1 and b = 2 and sign = -1, a*sign < b*sign returns false and swaps them..

    is the thing opposite here? as it seems that the order of the two elements being compared remains same when the condition is false.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Order of elements in a priority_queue is reversed.

      For example

      priority_queue<int, vector<int>, greater<int>>();
      

      is actually a minheap.


      For the case $$$a = 1$$$, $$$b = 2$$$ and $$$sign = -1$$$, the comparator return false, but it should be reversed so the order remain the same.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It is possible but you will have to maintain the priority_queue manually using make_heap, push_heap, and pop_heap.

https://ideone.com/jBJc9w

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

To change the comparator of the std::proiority_queue, you may use a type of struct/class called functor. It is a struct/class which has a function operator().

For example, to use a heap that its top element is the smallest one. You can write as follows.

Example

There is already functors in STL called greater<T> and less<T>. Code above can also write as follows:

...
priority_queue<int,vector<int>,greater<int> >q;
...

If you found mistakes in my code, please comment me.

And forgive me for my poor English.