Le tas est une structure importante dans la structure des données. Après avoir compris le concept et le fonctionnement du "tas", vous pouvez rapidement maîtriser le tri des tas.
Le concept de tas
Le tas est un arbre binaire complet spécial. Si les valeurs de tous les nœuds d'un arbre complètement binaire ne sont pas plus petites que leurs enfants, il est appelé un grand tas de racine (ou grand tas supérieur); Si les valeurs de tous les nœuds ne sont pas plus grandes que leurs enfants, elle est appelée un petit tas de racine (ou un petit tas supérieur).
Dans un tableau (stockant le nœud racine dans le numéro d'indice 0), il est facile d'obtenir l'équation suivante (ces deux équations sont très importantes):
1. Le nœud avec indice est i, et les coordonnées du nœud parent sont (i-1) / 2;
2. Le nœud avec indice est i, les coordonnées du nœud enfant gauche sont 2 * i + 1, et le nœud enfant droit est 2 * i + 2.
Établissement et entretien des tas
Le tas peut prendre en charge plusieurs opérations, mais maintenant nous ne nous soucions que de deux problèmes:
1. Compte tenu d'un tableau non ordonné, comment le construire comme un tas?
2. Après avoir supprimé l'élément supérieur du tas, comment ajuster la composition à un nouveau tas?
Regardons d'abord la deuxième question. Supposons que nous ayons déjà un grand tas de racines prêts à l'emploi. Maintenant, nous supprimons l'élément racine, mais nous ne déplaçons pas les autres éléments. Pensez à ce qui s'est passé: l'élément racine est vide, mais les autres éléments maintiennent toujours les propriétés du tas. Nous pouvons déplacer le dernier élément (nom de code A) vers la position de l'élément racine. S'il ne s'agit pas d'un cas particulier, les propriétés du tas sont détruites. Mais c'est simplement parce que A est plus petit qu'un de ses éléments enfants. Ainsi, nous pouvons changer A et cet élément enfant pour positionner. Si A est supérieur à tous ses éléments enfants, le tas est ajusté; Sinon, répétez le processus ci-dessus, l'élément A continue de "couler" dans la structure de l'arbre jusqu'à ce qu'il soit approprié, et le tableau restaure les propriétés du tas. Le processus ci-dessus est généralement appelé "dépistage", et la direction est évidemment de haut en bas.
Cela est vrai lors de la suppression d'un élément, tout comme l'insertion d'un nouvel élément. La différence est que nous mettons le nouvel élément à la fin, puis le comparons avec son nœud parent, c'est-à-dire le filtrer de bas en haut.
Alors, comment résoudre le premier problème?
De nombreux livres sur les structures de données que j'ai lus se filtraient du premier nœud non-feuille jusqu'à ce que l'élément racine soit filtré. Cette méthode est appelée «méthode de filtrage», qui nécessite des éléments de filtrage de boucle N / 2.
Mais nous pouvons également apprendre de l'idée de "créer quelque chose à partir de rien". Nous pouvons considérer le premier élément comme un tas, puis y ajouter constamment de nouveaux éléments. Cette méthode est appelée «méthode d'insertion», qui nécessite l'insertion de boucle d'éléments (n-1).
Étant donné que la méthode de filtrage et la méthode d'insertion sont différentes, les tas qu'ils créent sont généralement différents pour les mêmes données.
Après une compréhension approximative du tas, le tri du tas est une chose naturelle.
Aperçu de l'algorithme / idées
Nous avons besoin d'une séquence ascendante, que devons-nous faire? Nous pouvons construire un tas minimum, puis sortir l'élément racine à chaque fois. Cependant, cette méthode nécessite un espace supplémentaire (sinon elle provoquera beaucoup de mouvements d'éléments, et sa complexité montera sur O (n ^ 2)). Et si nous avons besoin de tri sur place (c'est-à-dire qu'il n'y a pas de complexité d'espace o (n) autorisée)?
Il y a un moyen. Nous pouvons construire le tas maximum, puis nous étendons la valeur maximale dans la dernière position, et la deuxième valeur maximale en dernière position ... puisque la sortie d'élément maximale libérera le premier espace, nous pouvons simplement placer un tel élément sans avoir besoin d'espace supplémentaire. Très belle idée, non?
classe publique heapsort {public static void main (String [] args) {int [] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20}; System.out.println ("Avant le tri:"); for (int i = 0; i <arr.length; i ++) {System.out.print (arr [i] + ""); } // theap tri Heapsort (arr); System.out.println (); System.out.println ("après après tri:"); for (int i = 0; i <arr.length; i ++) {System.out.print (arr [i] + ""); }} / ** * Tarit de tas * / private static void heapsort (int [] arr) {// Construisez la séquence à tri dans un grand tas supérieur pour (int i = arr.length / 2; i> = 0; i -) {heapadJust (arr, i, arr.length); } // échange progressivement le nœud racine de chaque valeur maximale avec l'élément final et ajustez l'arbre binaire pour en faire un grand tas supérieur pour (int i = arr.length - 1; i> 0; i--) {swap (arr, 0, i); // Échangez le record supérieur du tas avec le dernier enregistrement du tas de subséquence actuellement non trié (arr, 0, i); // Après l'échange, il est nécessaire de revérifier si le tas rencontre le tas de gros top. S'il ne se réunit pas, il doit être ajusté}} / ** * Processus de construction du tableau de tas * @param arral qui doit être trié * @param I Le numéro du nœud racine du tas qui doit être construit * @param n la longueur du tableau * / intchant static tas; int père; pour (père = arr [i]; LeftChild (i) <n; i = enfant) {child = Leftchild (i); // Si le sous-arbre gauche est plus petit que le sous-arbre droit, vous devez comparer le sous-arbre droit avec le nœud parent si (enfant! = N - 1 && arr [enfant] <arr [enfant + 1]) {enfant ++; // augmente le numéro de série de 1, pointant vers le sous-arbre droit} // Si le nœud parent est plus petit que le nœud enfant, vous devez échanger si (père <arr [enfant]) {arr [i] = arr [enfant]; } else {break; // La grande structure de tas supérieure n'est pas détruite, aucun ajustement n'est requis}} arr [i] = père; } // Obtenez le nœud enfant gauche privé static int Leftchild (int i) {return 2 * i + 1; } // Swap Element Position private static void swap (int [] arr, int index1, int index2) {int tmp = arr [index1]; arr [index1] = arr [index2]; arr [index2] = tmp; }}