0xb0 - Implementar una cola de prioridad

Una cola de prioridad (priority queue en inglés) es una estructura de datos que soporta por lo menos estas 3 operaciones:

• Insert(x, priority): Insertar un elemento x con prioridad priority.
• GetMax(): Encontrar el elemento cuya prioridad es máxima (sin borrarlo de la estructura).
• PopMax(): Borrar el elemento cuya prioridad es máxima.

Veamos una posible secuencia de operaciones como ejemplo:

• Inicialmente la estructura está vacía.
• Llamamos Insert("grafos", 1): Esto inserta el elemento "grafos" con prioridad 1.
• Llamamos GetMax(): Esto retorna "grafos", porque es el único elemento presente en la estructura (y por lo tanto, su prioridad es la máxima posible).
• Llamamos Insert("arreglos", 4): Inserta el elemento "arreglos" con prioridad 4.
• Llamamos GetMax(): Retorna "arreglos", porque la estructura tiene dos elementos ("grafos" y "arreglos") pero "arreglos" tiene mayor prioridad (4 vs 1).
• Llamamos PopMax(): Borra el elemento "arreglos", que es el que tiene mayor prioridad.
• Llamamos GetMax(): Retorna "grafos", porque otra vez es el único elemento.
• Llamamos Insert("recursividad", 2): Inserta "recursividad" con prioridad 2.
• Llamamos Insert("listas", 3): Inserta "listas" con prioridad 3.
• Llamamos GetMax(): Retorna "listas" (hay 3 elementos: "grafos", con prioridad 1; "recursividad", con prioridad 2; y "listas", con prioridad 3).
• Llamamos PopMax(): Borra "listas".
• Llamamos GetMax(): Retorna "recursividad".

Escribe un programa que implementa estas operaciones.

Entrada

La entrada contiene varias líneas:

• La primera línea contiene N, el número de operaciones a ejecutar.
• Luego vienen N líneas, cada una con una operación. Cada operación tiene uno de los posibles formatos:
  • Insert X P: Tu programa debe insertar el elemento X con prioridad P. X es una string formada exclusivamente con letras minúsculas y P es un número entero entre -109 y 109. La longitud de X siempre será mínimo 1 y máximo 20.
  • GetMax: Tu programa debe imprimir el elemento que tiene mayor prioridad. En caso de empate entre elementos con la misma prioridad, tu programa debe imprimir el que sea menor alfabéticamente.
  • PopMax: Tu programa debe borrar el elemento con mayor prioridad. En caso de empate entre elementos con la misma prioridad, tu programa debe borrar el que sea menor alfabéticamente.

Está garantizado que GetMax y PopMax nunca aparecerán en la entrada cuando la estructura está vacía.

Salida

Por cada una de las operaciones GetMax, tu programa debe imprimir una sóla línea con el elemento que tiene mayor prioridad en ese momento (resolviendo empates como se explicó más arriba).

Entrada de ejemplo #1

11
Insert grafos 1
GetMax
Insert arreglos 4
GetMax
PopMax
GetMax
Insert recursividad 2
Insert listas 3
GetMax
PopMax
GetMax

Salida de ejemplo #1

grafos
arreglos
grafos
listas
recursividad

Explicación del ejemplo #1

Este es el ejemplo del enunciado del problema.

Entrada de ejemplo #2

5
Insert codeo 100
Insert twitter 100
GetMax
PopMax
GetMax

Salida de ejemplo #2

codeo
twitter

Explicación del ejemplo #2

En caso de empate entre dos elementos con la misma prioridad, tu programa debe imprimir (ó borrar) el elemento más pequeño alfabéticamente.

Entrada de ejemplo #3

11
Insert codeo 5
Insert codeo 3
Insert codeo 4
Insert codeo 6
GetMax
PopMax
GetMax
PopMax
GetMax
PopMax
GetMax

Salida de ejemplo #3

codeo
codeo
codeo
codeo

Explicación del ejemplo #3

Si todos los elementos son iguales, la prioridad no importa mucho porque la salida siempre es la misma.

Entrada de ejemplo #4

17
Insert codeo 100
Insert codeo 100
Insert twitter 1
Insert books 50
Insert sleep 50
GetMax
PopMax
Insert books 50
GetMax
PopMax
GetMax
PopMax
GetMax
PopMax
GetMax
PopMax
GetMax

Salida de ejemplo #4

codeo
codeo
books
books
sleep
twitter

Explicación del ejemplo #4

¡Es posible que el mismo elemento aparezca dos veces con la misma prioridad! Tu programa no debe descartar los repetidos.

Entrada de ejemplo #5

3
Insert a 1
Insert aa 1
GetMax

Salida de ejemplo #5

a

Explicación del ejemplo #5

En este caso hay empate entre a y aa, pero a gana porque es lexicográficamente menor (en general, si una string es S es un prefijo de T, entonces S es lexicográficamente menor a T).

Restricciones

• En aproximadamente 50% de los casos, el número de operaciones N satisface 1 ≤ N ≤ 100.
• En el resto de los casos, N satisface 1 ≤ N ≤ 100,000.

Envía tu solución