На каква структура от данни е базирана стандартната библиотечна опашка с приоритет (priority_queue)?

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