c++ - 不期望 priority_queue 的顺序

Question

我有以下定义:

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 被修改了几次。

Answer 1

如前所述，如果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();
}