Un tas binaire est un tas spécial. Un tas binaire est un arbre binaire complet (arbre binaire) ou un arbre binaire approximativement complet (arbre binaire). Il existe deux types de tas binaires: le plus grand tas et le plus petit tas. Tas maximum: la valeur clé du nœud parent est toujours supérieure ou égale à la valeur clé de tout nœud enfant; Tas minimum: la valeur clé du nœud parent est toujours inférieure ou égale à la valeur clé de tout nœud enfant.
Tas de binaire imprimé: utilisez des relations hiérarchiques
Ici, je trie d'abord le tas, puis je exécute la méthode pour imprimer le tas en tri printAsTree()
La classe publique Maxheap <t s'étend comparable <? Super T >> {Données privées T []; Taille INT privée; capacité int privée; public maxheap (int la capacité) {this.capacity = capacité; this.size = 0; this.data = (t []) nouveau comparable [capacité + 1]; } public maxHeap (t [] arr) {// taspify, array tas capacity = arr.length; data = (t []) Nouveau comparable [capacité + 1]; System.ArrayCopy (Arr, 0, Data, 1, Arr.Length); size = arr.length; for (int i = size / 2; i> = 1; i--) {shiftDown (i); }} public int size () {return this.size; } public int getCapacity () {return this.capacity; } public boolean isEmpty () {return size == 0; } public t SeekMax () {return data [1]; } public void swap (int i, int j) {if (i! = j) {t temp = data [i]; data [i] = data [j]; data [j] = temp; }} public void insert (t item) {size ++; data [size] = item; ShifUp (taille); } public t popmax () {swap (1, size--); décalage (1); Retour des données [taille + 1]; } public void shipUp (int child) {while (enfant> 1 && data [enfant] .compareto (data [enfant / 2])> 0) {swap (enfant, enfant / 2); enfant / = 2; }} / ** * @param Une marque d'angle inférieure d'un élément dans le tableau de données * @param b marque de coin inférieur d'un élément dans le tableau de données * @return return quel élément est plus grand, la marque de coin inférieure dont l'élément est plus grand * / privé int max (int a, int b) {if (data [a] .compareto (data [b]) <0) {// si les données [b] big b; Données [A] Big Return A; // Renvoie A}} / ** * @param Une marque de coin inférieure d'un élément dans le tableau de données * @param B Bas Corner Mark d'un élément dans le tableau de données * @param C la marque d'angle inférieure d'un élément dans le tableau de données * @return la marque de coin inférieure dont l'élément est plus grand * / privé int Max (int a, int b, int c) {int bancal = max (a, b); plus grand = max (plus grand, c); retour plus grand; } public void shipdown (int père) {while (true) {int lChild = père * 2; int rchild = père * 2 + 1; int newfather = père; // peu importe si la mission est attribuée ici. Si le rendement suivant est modifié en cassant, il doit être attribué si (lChild> taille) {// s'il n'y a pas d'enfants à gauche et à droite renvoient; } else if (rchild> size) {// s'il n'y a pas de bon enfant newfather = max (père, lChild); } else {// s'il y a un enfant gauche et droit newfather = max (père, lchild, rchild); } if (newfather == père) {// Si le nœud parent d'origine est le plus grand des trois, vous n'avez pas besoin de continuer à régler le retour du pile; } else {// Le nœud parent n'est pas le plus grand, échangez les enfants plus âgés et continuez à ajuster la baisse jusqu'à ce que le grand tas de racine soit satisfait d'échange (nouveau, père); père = nouveau-père; // équivalent à Switchdown (nouveau). Si le nouveau se révèle être l'enfant gauche du père, il est équivalent à Shiftdown (2 * père)}}} public statique <t s'étend comparable <? super t >> void tri (t [] arr) {int len = arr.length; MaxHeap <T> maxHeap = new maxHeap <> (arr); maxheap.printastree (); for (int i = len - 1; i> = 0; i--) {arr [i] = maxHeap.popMax (); }} public static void printarr (objet [] arr) {for (objet o: arr) {System.out.print (o); System.out.print ("/ t"); } System.out.println (); } public void printpace (int n) {// imprimer n espaces (utilisé avec '/ t' ici à la place) pour (int i = 0; i <n; i ++) {System.out.printf ("% 3s", ""); }} public void printastree () {int linenum = 1; // Traverse la première ligne int line = (int) (math.log (size) / math.log (2)) + 1; // lignes est le nombre de couches du tas int spacenum = (int) (math.pow (2, lignes) - 1); pour (int i = 1; i <= taille;) {// Parce que les données sont stockées dans l'intervalle fermé gauche et droit dans [1 ... Taille], les données [0] ne stockent pas les données // Chaque couche imprime cet intervalle [2 ^ (numéro de couche 1) ... (2 ^ Numéro de couche) -1]. Si le nombre dans le tas n'est pas suffisant (2 ^ couches) -1, imprimez à la taille. Alors prenez min ((2 ^ couches) -1, taille). pour (int j = (int) math.pow (2, linenum - 1); j <= math.min (taille, (int) math.pow (2, linenum) - 1); j ++) {printspace (spacenum); // Imprimez des espaces avec Spacenum System.out.printf ("% 3s", données [J]); // imprimer des données System.out.printf ("% 3s", ""); // Boîte verte dans l'espace d'image (Espacem); // Imprimez des espaces avec Spacenum I ++; // Chaque élément est imprimé, il s'agit de + 1} linenum ++; Spacenum = Spacenum / 2; System.out.println (); }} public static void main (String args []) {entier [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6, 1, 3, 6, 1, 1}; tri (arr); }}Résultats de l'exécution:
Résumer
Ce qui précède est tout le contenu de cet article sur le partage de code d'impression de la langue java qui implémente des tas binaires. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!