На какой структуре данных основана стандартная библиотечная очередь с приоритетом (priority_queue)?

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