Algorithmes et Structures de Données

Corriger le tas

Étant donné un max-heap (tas max) contenant n nombres, tous les éléments respectent la propriété de max-heap à l’exception de la racine. Vous devez réparer ce tas pour que tous les nombres présents satisfassent effectivement la propriété de max-heap.

Entrée

La première ligne de l’entrée contient un seul entier n (1 ≤ n ≤ 100 000).

La ligne suivante contient n entiers séparés par des espaces, notés (), qui représentent les valeurs des éléments du tas.

Sortie

Le programme doit afficher n entiers séparés par des espaces, correspondant au tas réparé.

Exemples

Entrée

Sortie

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

Explications

profound.academy-Heap-3.1.drawio.png
Exemple 1 illustré. Le graphique de gauche représente le tas initial. Celui de droite montre le tas après correction.

profound.academy-Heap-3.2.drawio.png
Exemple 2 illustré. Le graphique de gauche représente le tas initial. Celui de droite montre le tas après correction.

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