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

Exemple 1 illustré. Le graphique de gauche représente le tas initial. Celui de droite montre le tas après correction.
Exemple 1 illustré. Le graphique de gauche représente le tas initial. Celui de droite montre le tas après correction.
 
Exemple 2 illustré. Le graphique de gauche représente le tas initial. Celui de droite montre le tas après correction.
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