¿En qué estructura de datos se basa la cola de prioridad estándar de la biblioteca (priority_queue)?

Montículo (heap). En particular, un max-heap por defecto, que proporciona acceso al elemento máximo en $O(1)$. Las operaciones de inserción y eliminación toman $O(\log N)$, donde $N$ es la cantidad de elementos.