Eficiencia de la cola de prioridad STL

Tengo una aplicación (C ++) que creo que sería útil para un STLpriority_queue. La documentación dice:

Priority_queue es un adaptador de contenedor, lo que significa que se implementa sobre algún tipo de contenedor subyacente. Por defecto, ese tipo subyacente es vector, pero se puede seleccionar explícitamente un tipo diferente.

y

Las colas de prioridad son un concepto estándar y pueden implementarse de muchas maneras diferentes; Esta implementación utiliza montones.

Tuve previamenteficticio esetop() esO(1), y esopush() seria unO(logn) (las dos razones por las que elegí elpriority_queue en primer lugar), pero la documentación no confirma ni niega esta suposición.

Profundizando, los documentos para el concepto de secuencia dicen:

Las complejidades de inserción y borrado de un solo elemento dependen de la secuencia.

lospriority_queue usa unvector (de forma predeterminada) como un montón, que:

... admite acceso aleatorio a elementos, inserción y eliminación de elementos en tiempo constante al final, e inserción y eliminación de elementos en tiempo lineal al principio o en el medio.

Estoy deduciendo eso, usando el valor predeterminadopriority_queue, top() esO(1) ypush() esO(n).

Pregunta 1: ¿Es esto correcto? (top() el acceso esO(1) ypush() esO(n)?)

Pregunta 2: ¿Sería capaz de lograrO(logn) eficiencia enpush() si usara unset (omultiset) en vez de unavector para la implementación de lapriority_queue? ¿Cuáles serían las consecuencias de hacer esto? ¿Qué otras operaciones sufrirían como consecuencia?

N.B .: Me preocupa la eficiencia del tiempo aquí, no el espacio.