Auf welcher Datenstruktur basiert die Standardbibliotheks-Warteschlange mit Priorität (priority_queue)?

Куча (heap). В частности, max-heap по умолчанию, обеспечивая доступ к максимальному элементу за $O(1)$. Операции вставки и удаления занимают $O(\log N)$, где $N$ — количество элементов.