Cola de prioridad usando pila

Question

Se puede construir una cola de prioridad utilizando pilas, de modo que la cola prioritaria tenga la misma complejidad de cada operación. ¿Se podría hacer?¿Si es así, cómo?Si no, ¿cuál es la mejor solución que se puede hacer?

Cada operación de una pila utilizando una matriz es $ o (1) $ , mientras que casi todas las operaciones de la cola prioritaria son $ O (logn) $ . Se puede realizar una implementación utilizando $ 2d $ pilas, cada elemento de la pila es nuevamente una pila. Cuando el primer elemento de la pila principal es el primer elemento de las otras pilas. La operación de DEQUEUE tomará $ o (n) $ como es Lifo y la cola de prioridad es FIFO.

Answer 1

Piénsalo.Puede ordenar una matriz agregando todos los elementos a una cola de prioridad, luego eliminando los artículos en orden ordenado.

Si puede ejecutar una cola prioritaria en un tiempo constante, podría ordenar un tiempo lineal.Pero no puedes.