Wie aktualisiert man Elemente innerhalb einer 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; 
} 

hat ich eine Prioritätswarteschlange und 3 eingeführt Knoten (struct) in der Prioritätswarteschlange und dann geändert I den Wert des mittleren Elements in der Warteschlange kann jedoch nicht, wie die Prioritätswarteschlange zu aktualisieren, nachdem das Element zu aktualisieren?

Answer 1

Die Prioritätswarteschlange soll mit festen Prioritäten arbeiten, d. H. Die Elementpriorität sollte zum Zeitpunkt des Einfügens bekannt sein und dann gleich bleiben. Aus diesem Grund werden alle Vergleiche durchgeführt, wenn das Element in die Warteschlange geschoben wird.

Wenn Sie einen sortierten Container wünschen, in dem Sie die Schlüssel ändern können, versuchen Sie std::multimap. Es würde Ihnen erlauben, jedes Element zu entfernen und wird sich selbst neu ausbalancieren. Wenn Sie es von begin() zu end() durchsuchen, besuchen Sie Ihre node s in der gewünschten Reihenfolge.

Leider müssen Sie immer noch das Element entfernen und einfügen, um den Schlüssel zu ändern, hoffentlich wird C++ 17 etwas dagegen tun.