¿Cuándo se ordena una std :: priority_queue <>?

Question

Me preguntaba cuándo se clasifica el C++ STL priority_queue. Me refiero a insert en un lugar correcto cuando push el artículo en, o se clasifica a sí mismo y le da el elemento de mayor prioridad cuando peek o pop a cabo? Pregunto esto porque mi priority_queue<int> contendrá un índice a una matriz que puede tener valores actualizados, y quiero que se actualice cuando lo haga pq.top();.

#include <cstdio> 
#include <algorithm> 
#include <queue> 
using namespace std; 

int main() { 
    priority_queue<int> pq; 
    pq.push(2); 
    pq.push(5); //is the first element 5 now? or will it update again when I top() or pop() it out? 
    return 0; 
} 

Thanks.

Answer 1

El trabajo se realiza durante push() y pop(), que llamar a las funciones de modificación montón subyacentes (push_heap() y pop_heap()). top() toma un tiempo constante.

Answer 2

Se ordena solo cuando se inserta un nuevo elemento o se elimina uno existente. This might help.

Answer 3

método std :: priority_queue :: push/(y emplace) causa un reordenamiento eficiente en el montón.

http://www.cplusplus.com/reference/queue/priority_queue/emplace/