Algorithme de tri par tas (Heap sort)
Le tri par tas (heap sort) est un algorithme de tri basé sur la comparaison qui utilise une structure de données appelée tas (heap) pour organiser les éléments d’un tableau. Le principe de base consiste d’abord à transformer les éléments du tableau en un tas. Ensuite, on enlève de façon répétée l’élément le plus grand ou le plus petit (selon qu’il s’agit d’un tas maximum ou d’un tas minimum) pour le placer à la fin du tableau. Cette opération est répétée jusqu’à ce que le tas soit vide.
Dans ce cours, vous devez implémenter l’algorithme de tri par tas en utilisant un tas minimum.
Données en entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000), qui représente le nombre d’éléments.La ligne suivante contient
n entiers séparés par des espaces, (), qui sont les valeurs à trier.Sortie
Le programme doit afficher le tableau final trié dans l’ordre croissant.
Exemples
Entrée | Sortie |
7
4 3 8 -2 9 0 2 | -2 0 2 3 4 8 9 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB