Эффективность STL priority_queue
У меня есть приложение (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
? Каковы будут последствия этого? Какие другие операции пострадают в результате?
Н.Б .: Я беспокоюсь об эффективности времени, а не пространства.