У меня есть priority_queue, и я хочу изменить егоs содержимое (значение приоритета), будет ли тогда очередь восстанавливаться?

Это зависит от того, использует ли он push / pop (более вероятно, потому что вам просто нужно "вставить», а не прибегать целиком), или при доступе к топу или поп.

Я действительно хочу изменить некоторые элементы в очереди. Что-то вроде того:

priority_queue q;

int a=2,b=3,c=5;
int *ca=&a, *cb=&b, cc=&c;

q.push(a);
q.push(b);
q.push(c); //q is now {2,3,5}

*ca=4;

//what happens to q?
// 1) {3,4,5}
// 2) {4,2,5}
// 3) crash