我有以下定义:
struct vertex {
int number;
bool mixed = false;
vertex(int n):number(n){};
bool operator > (const vertex & v)const{
return d[this->number] > d[v.number];
}
与
priority_queue<vertex, vector<vertex>, greater<vertex> >q
调试后,我发现队列没有按我预期的那样排序(按照数组 d 的顺序)。我想知道为什么。在此过程中,数组 d 被修改了几次。
最佳答案
如前所述,如果x
已经存储在priority_queue
中并且您修改d[x]
,您将破坏您的数据结构。
一个明显的解决方案是删除元素,更改 d
然后将其放回原处。
据我所知,priority_queue
不允许随机访问删除,因此您可以使用 set
。 set.begin()
返回最低的元素。
void update(int x, int v) {
set.erase(x);
d[x] = v;
set.insert(x);
}
int getMin() {
return *set.begin();
}
关于c++ - 不期望 priority_queue 的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54272567/