import java.util.Random;

class Arbre {
    Noeud racine;
    Arbre() {}
    boolean nonVide() { return racine != null; }


    // construction d'un tas à partir d'un tableau. Tout noeud qui n'est pas
    // une feuille contient une étiquette pointant vers la plus grande valeur
    // pointée par ses fils.
    Arbre (int[] tab, int debut, int fin) {
	if (debut < fin){
	    Arbre 
		a = new Arbre(tab, debut, (debut + fin)/2), 
		b = new Arbre(tab, (debut + fin)/2 + 1, fin);
	    racine = new Noeud(maximum(a.racine.cle,b.racine.cle),a, b);
	}
	else if (debut == fin) racine = new Noeud(new Integer(tab[debut]));
    }

    // renvoie un pointeur vers la plus grande des deux étiquettes x et y
    static Integer maximum(Integer x, Integer y) {
	if (x == null) return y;
	if (y == null) return x;
	return (x.intValue() > y.intValue()) ? x : y;
    }
    
    // simule le remplacement de la plus grande valeur par moins l'infini,
    // avec mise à jour des étiquettes. Renvoie un pointeur vers le 
    // nouveau maximum.
    Integer ajuster(Integer suppr) {
	if (this.nonVide()) {
	    if (suppr == racine.cle) {
		Integer newMaxG =  racine.gauche.ajuster(suppr);
		Integer newMaxD =  racine.droit.ajuster(suppr);
		racine.cle = maximum(newMaxG, newMaxD);
	    }
	    return racine.cle;
	}
	return null;
    }

    // extrait le maximum, met à jour les étiquettes, et renvoie la valeur 
    // extraite.
    int extraireMax() {
	int r = racine.cle.intValue();
	ajuster(racine.cle);
	return r;
    }
}

class Noeud {
    // la cle d'un noeud pointe vers un entier encapsule, ou vers null
    // si elle représente moins l'infini.
    Integer cle;
    Arbre gauche = new Arbre();
    Arbre droit  = new Arbre();
    
    Noeud() {}  
    Noeud(Integer n) { cle = n; }
    Noeud(Integer n, Arbre g, Arbre d) { cle = n; gauche = g; droit = d; } 
}

public class Exercice_5_3{

    static void tri(int[] tab) {
	int i;
	Arbre a = new Arbre(tab, 0, tab.length - 1);
	for (i = tab.length - 1 ; i >= 0; i--)
	    tab[i] = a.extraireMax();
    }

    static void remplissageAleatoire(int[] tab, int MAX){
	int i;
	Random aleatoire = new Random();
	for(i=0; i< tab.length ; i++) tab[i] = (int) (aleatoire.nextFloat() * MAX);
    }

    static String chaine(int[] tab){
	int i;
	String s = "";

	for (i=0; i<tab.length ;i++) s+= tab[i] + " "; 
	return s;
    }

    public static void main(String[] args){
	int[] tab = new int[20];
	remplissageAleatoire(tab,100);

	System.out.println("Le tableau initial : "+chaine(tab));
	tri(tab);
	System.out.println("Le tableau trie :    "+chaine(tab));
  }
}