How to update elements inside an std::priority_queue?

Question

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <stdio.h>
#include <list>
#include <string.h>
#include <queue>
#include <algorithm>
#define pb push_back
using namespace std;
typedef pair<int,int> ii;


struct node{
    int digit;
};


class Compare{
public:
    bool operator()(node* a,node* b){
        return (a->digit)>(b->digit);
    }
};


int main()
{
priority_queue<node*,vector<node*>,Compare> pq;
vector<node*> vec;
node* p = new node();
node* q = new node();
node* r = new node();
p->digit=100;
q->digit=200;
r->digit=300;
pq.push(p);
pq.push(q);
pq.push(r);
q->digit=50;
pq.push(nod);
while(!pq.empty()){
    cout<<(pq.top())->digit<<endl;
    pq.pop();
}
return 0;
}

I created a priority queue and inserted 3 nodes(struct) in the priority queue and then I changed the value of the middle element present in the queue but cannot figure out how to update the priority queue after updating the element ?

Answer 1

Priority queue is intended to work with fixed priorities, i.e. element priority should be known at the moment of insertion and then stay the same. That is why all the comparisons are done when the element is pushed into the queue.

If you want a sorted container that would let you change the keys, try std::multimap. It would allow you to remove any element and will rebalance itself. Traversing it from begin() to end() will visit your nodes in the desired order.

Unfortunately you'll still have to remove and insert the element to change the key , hopefully C++17 will do something about it.