Algoritmos y Estructuras de Datos

Arreglar el montículo (max-heap)

Se tiene un max-heap con n números, donde todos los elementos cumplen la propiedad de max-heap excepto la raíz. El objetivo es corregir el montículo y asegurarse de que todos los números en él cumplan realmente la propiedad de max-heap.

Entrada

La primera línea de la entrada contiene un único entero n (1 ≤ n ≤ 100 000).
La siguiente línea contiene n números separados por espacios (), que representan los valores de los elementos en el montículo.

Salida

El programa debe imprimir n números separados por espacios que representen el montículo corregido.

Ejemplos

Entrada
Salida
7 -1 9 7 1 3 6 5
9 5 7 1 -1 6 3
8 -2 7 5 2 1 3 4 1
7 2 5 1 1 3 4 -2

Explicación

Demostración del ejemplo 1. El gráfico de la izquierda representa el montículo inicial. El de la derecha muestra el montículo ya corregido.
Demostración del ejemplo 1. El gráfico de la izquierda representa el montículo inicial. El de la derecha muestra el montículo ya corregido.
 
Demostración del ejemplo 2. El gráfico de la izquierda representa el montículo inicial. El de la derecha muestra el montículo ya corregido.
Demostración del ejemplo 2. El gráfico de la izquierda representa el montículo inicial. El de la derecha muestra el montículo ya corregido.
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue