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

由于您使用 d 作为 priority_queue 排序的一部分，一旦您开始向队列中添加内容，就无法对其进行更改。这样做可能会更改队列中包含的对象的顺序，并会破坏用于 priority_queue.

的比较所需的 严格弱排序

此外，priorty_queue are not completely sorted, because it is implemented using a heap.

内的元素

Answer 2

如前所述，如果x已经存储在priority_queue中，而你修改d[x]，你将破坏你的数据结构。一个明显的解决方案是删除元素，更改 d 然后将其放回原处。 AFAIK，priority_queue 不允许随机访问删除，因此您可以使用 set。 set.begin() returns 最低元素。

void update(int x, int v) {
  set.erase(x);
  d[x] = v;
  set.insert(x);
}

int getMin() {
  return *set.begin();
}

priority_queue 的顺序不是预期的

order of priority_queue not expected

c++

priority-queue