Fila de prioridade usando a pilha

Question

Pode criar uma fila prioritária usando pilhas, de modo que a fila prioritária tenha a mesma complexidade para cada operação. Poderia ser feito?Em caso afirmativo, como?Se não, qual é a melhor solução que pode ser feita?

Cada operação de uma pilha usando uma matriz é $ o (1) $ Considerando que quase toda a operação da fila prioritária é $ O (logn) $ . Uma implementação pode ser feita usando $ 2D $ pilhas, cada elementos da pilha é novamente uma pilha. Quando o primeiro elemento da pilha principal é o primeiro elemento das outras pilhas. A operação de dequeue levará $ O (n) $ como é lifo e a fila prioritária é FIFO.

Answer 1

Pense nisso.Você pode classificar uma matriz adicionando todos os itens a uma fila prioritária e, em seguida, removendo os itens em ordem classificada.

Se você pudesse executar uma fila prioritária em tempo constante, você pode classificar no tempo linear.Mas você não pode.