Traduction en C#
Tri par arbre Heapsort
 
Une classe C# solution du problème :

Les 3 sous programmes C#  implantant l'algorithme de tri par arbre :
Les variables  P et tas[] sont statiques (ce sont des variables de classe)
 
static int Supprimer ( )
      {
        int Lemini, i ;
       // retourne  la racine (minimum actuel) pour stockage éventuel :
         Lemini = tas[1] ;
         tas[1] = tas[P] ; // la racine prend la valeur de la dernière feuille de l'arbre
         P = P - 1 ; 
        int j = 1 ; 
        while (j <= (P / 2)) {
           // recherche de l'indice i du plus petit des descendants de tas[j]
          if ((2 * j == P ) | (tas[2 * j] < tas[2 * j + 1]))   i = 2 * j ;
          else i = 2 * j +1 ;
          // Echange éventuel entre tas[j] et son fils tas[i]
          if (tas[j] > tas[i] ) {
             int  temp = tas[j] ;
               tas[j] = tas[i] ;
               tas[i] = temp ;
               j = i ;
          }
          else break ;
        }
        return Lemini;
      }
static void Ajouter ( int x ) 
            {
                P++; 
               int j = P; 
                tas[P] = x; 
               while ( (j > 1) && (tas[j] < tas[j / 2]) ) {
                  int temp = tas[j] ; 
                   tas[j] = tas[j / 2] ; 
                   tas[j / 2] = temp ; 
                   j = j / 2 ; 
              }
             } 

Notons que l'opérateur booléen optimisé '&&' évite l'effet de bord lorsque j<1 (c-à-d ici j = 0 ). Il n'est donc pas necessaire de mettre une sentinelle dans tas[0], puisque dès j vaut 0 le reste de l'expression n'est pas évaluée !

Les variables Lemin, TabInit[] et TabTrie[] sont statiques (ce sont des variables de classe)
static void Tri_Arbre() 
      {
         P = 0;
        // construction du tas :
        while (P < max)
          Ajouter(TabInit[P+1]); // appel de l'algorithme Ajouter

        // sortie et élimination des minima successifs : 
        while (P >= 1) {
            Lemin = Supprimer() ; // appel de l'algorithme Supprimer
            TabTrie[max-P] = Lemin ; // stockage du minimum dans le nouveau tableau
        }

 

Une classe complète permettant l'exécution des sous-programmes précédents :
 
using System;
namespace CsExosAlgo1
{
class ApplicationTriHeapSort {
 

static int[] table ; // le tableau à trier 
static int max = 19; // les cellules utiles vont de 1 à 19.(de 1 à table.length-1)
static int[] TabInit = new int[max+1] ; // les données initiales dans un tableau 
static int[] tas = new int[max+1] ; // le tas, la cellule tas[0]  peut contenir une sentinelle
static int[] TabTrie = new int[max+1] ; // le tableau une fois trié 
static int P, Lemin;
    static void AfficherTable ( int[] table ) {
     // Affichage du tableau sans la sentinelle
        int n = table.Length-1;
        for ( int i = 1; i <= n; i++) 
            System.Console.Write (table[i]+" , ");
         System.Console.WriteLine ( );
    }

    static void InitTable  ( ) 
    { // sentinelle dans la cellule de rang zéro
        int[ ] tableau = { Int32.MinValue ,14 , 35 , 84 , 49 , 50 , 94 , 89 , 58 , 61 , 47 ,
                                  39 , 58 , 57 , 99 , 12 , 24 , 9 , 81 , 80 };
        table = tableau; // original conservé si nécessaire
        for ( int i = 1; i <= table.Length-1; i++)        
           TabInit[i] = table[i]; // on va travailler sur ce tableau
    }

 static void Main(string[ ] args) {
         InitTable ( );
         System.Console.WriteLine("Tableau initial :");
         AfficherTable (TabInit );
         Tri_Arbre();
         System.Console.WriteLine("Tableau une fois trié :");
         AfficherTable (TabTrie );
         System.Console.Read();
  }
static void Ajouter ( int x )
      {
         P++;
        int j = P;
         tas[P] = x;
        while ( (j > 1)&& (tas[j] < tas[j / 2]) ) {
          int temp = tas[j] ;
            tas[j] = tas[j / 2] ;
            tas[j / 2] = temp ;
            j = j / 2 ;
        }
      }

static int Supprimer ( )
      {
        int Lemini, i ;
         Lemini = tas[1] ; // retourne  la racine (minimum actuel) pour stockage éventuel
         tas[1] = tas[P] ; // la racine prend la valeur de la dernière feuille de l'arbre
         P = P - 1 ; 
        int j = 1 ; 
        while (j <= (P / 2)) {
           // recherche de l'indice i du plus petit des descendants de tas[j]
          if ((2 * j == P ) | (tas[2 * j] < tas[2 * j + 1]))   i = 2 * j ;
          else i = 2 * j +1 ;
          // Echange éventuel entre tas[j] et son fils tas[i]
          if (tas[j] > tas[i] ) {
             int  temp = tas[j] ;
               tas[j] = tas[i] ;
               tas[i] = temp ;
               j = i ;
          }
          else break ;
        }
        return Lemini;
      }

static void Tri_Arbre() 
      {
         P = 0;
        // construction du tas :
        while (P < max)
          Ajouter( TabInit[P+1] ); // appel de l'algorithme Ajouter

        // sortie et élimination des minima successifs : 
        while (P >= 1) {
            Lemin = Supprimer( ) ; // appel de l'algorithme Supprimer
            TabTrie[max-P] = Lemin ; // stockage du minimum dans le nouveau tableau
        }
      }
 }
}

Source recopiable (cliquez sur le lien)
 
 

Tableau initial :
14 , 35 , 84 , 49 , 50 , 94 , 89 , 58 , 61 , 47 , 39 , 58 , 57 , 99 , 12 , 24 , 9 , 81 , 80

Tableau une fois trié :
9 , 12 , 14 , 24 , 35 , 39 , 47 , 49 , 50 , 57 , 58 , 58 , 61 , 80 , 81 , 84 , 89 , 94 , 99
 
 

Remonter