У меня есть приложение (C ++), которое, я думаю, будет хорошо обслуживаться STLpriority_queue. Документация говорит:

Priority_queue - это адаптер контейнера, что означает, что он реализован поверх некоторого базового типа контейнера. По умолчанию этот базовый тип является векторным, но другой тип может быть выбран явно.

а также

Очереди приоритетов являются стандартной концепцией и могут быть реализованы различными способами; эта реализация использует кучи.

Я раньшепредполагается, тотtop() являетсяO(1)и чтоpush() будетO(logn) (две причины я выбралpriority_queue в первую очередь) - но документация не подтверждает и не опровергает это предположение.

Копая глубже, документы для концепции последовательности говорят:

Сложности одноэлементной вставки и стирания зависят от последовательности.

priority_queue используетvector (по умолчанию) в виде кучи, которая:

... поддерживает произвольный доступ к элементам, постоянное время вставки и удаления элементов в конце и линейное время вставки и удаления элементов в начале или в середине.

Я предполагаю, что, используя по умолчаниюpriority_queue, top() являетсяO(1) а такжеpush() являетсяO(n).

Вопрос 1: Это правильно? (top() доступO(1) а такжеpush() являетсяO(n)?)

Вопрос 2: Смогу ли я достичьO(logn) эффективность наpush() если бы я использовалset (или жеmultiset) вместоvector для реализацииpriority_queue? Каковы будут последствия этого? Какие другие операции пострадают в результате?

Н.Б .: Я беспокоюсь об эффективности времени, а не пространства.