CODEWITHSUNDEEP
c++priority-queue
bright yang
bright yang

Reputation: 99

order of priority_queue not expected

I have the following definitions:

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];
}

with

priority_queue<vertex, vector<vertex>, greater<vertex> >q

after my debugging, I found the queue not sorted as I expected ( following the order of array d ). I wonder why. During the process array d is modified serveral times.

Upvotes: 1

Views: 69

Answers (2)

user2956272
user2956272

Reputation:

As mentioned before, if x is already stored in priority_queue and you modify d[x], you will destroy your data structure. An obvious solution is to remove element, change d and then place it back. AFAIK, priority_queue doesn't allow random-access removals, so you can use set. set.begin() returns the lowest element. 

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

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

Upvotes: 1

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

Since you're using d as part of the ordering for your priority_queue, you can't make changes to it once you start adding things to the queue. Doing so would potentially change the ordering of the objects contained in the queue, and would break the strict weak ordering required of the comparison used for a priority_queue.

In addition, the elements within a priorty_queue are not completely sorted, because it is implemented using a heap.

Upvotes: 1

Related Questions