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

profound.academy-Heap-3.1.drawio.png
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.

profound.academy-Heap-3.2.drawio.png
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