Eficiência da fila de prioridade do STL
Eu tenho um aplicativo (C ++) que acho que seria bem servido por um STLpriority_queue
. A documentação diz:
Priority_queue é um adaptador de contêiner, o que significa que ele é implementado sobre algum tipo de contêiner subjacente. Por padrão, esse tipo subjacente é vetor, mas um tipo diferente pode ser selecionado explicitamente.
e
Filas prioritárias são um conceito padrão e podem ser implementadas de várias maneiras diferentes; essa implementação usa pilhas.
Eu tinha anteriormenteassumido estetop()
éO(1)
, e essapush()
seria umO(logn)
(as duas razões pelas quais escolhi opriority_queue
em primeiro lugar) - mas a documentação não confirma nem nega essa suposição.
Indo mais fundo, os documentos do conceito Sequência dizem:
As complexidades da inserção e eliminação de um único elemento dependem da sequência.
opriority_queue
usa umvector
(por padrão) como um heap, que:
... suporta acesso aleatório a elementos, inserção e remoção constantes de tempo no final e inserção e remoção linear de tempo no início ou no meio.
Estou deduzindo que, usando o padrãopriority_queue
, top()
éO(1)
epush()
éO(n)
.
Questão 1: Isso está correto? (top()
o acesso éO(1)
epush()
éO(n)
?)
Questão 2: Eu seria capaz de alcançarO(logn)
eficiência empush()
se eu usasse umset
(oumultiset
) em vez de umvector
para a implementação dopriority_queue
? Quais seriam as consequências de fazer isso? Que outras operações sofreriam como consequência?
N.B .: Estou preocupado com a eficiência do tempo aqui, não com o espaço.