Coda prioritaria usando la pila

Question

può creare una coda prioritaria utilizzando Stacks, in modo tale che la coda prioritaria abbia la stessa complessità per ogni operazione. Potrebbe essere fatto?Se é cosi, come?Se no, qual è la soluzione migliore che può essere fatta?

Ogni operazione di uno stack usando un array è $ o (1) $ considerando che quasi tutte le operazioni di coda prioritaria è $ O (logn) $ . Un'implementazione può essere eseguita utilizzando $ 2D $ pile, ciascun elementi della pila è di nuovo una pila. Quando il primo elemento dello stack principale è il primo elemento degli altri pile. L'operazione Dequeue prenderà $ o (n) $ come è lifo e la coda prioritaria è FIFO.

Answer 1

pensa a questo.È possibile ordinare un array aggiungendo tutti gli elementi a una coda prioritaria, quindi rimuovendo gli elementi in ordine ordinato.

Se è possibile eseguire una coda prioritaria in costante tempo, è possibile ordinare in tempo lineare.Ma non puoi.