import java.util.ArrayList;

/*On considere ici un tableau ou une liste indice(e) a partir de 0.
On appelle pere de la "case" qui se trouve a l'indice i  (ici appele noeud i) le noeud (i -1 )/2 (si i > 0). 
On appelle fils d'un noeud i les noeuds 2 * i + 1 et 2 * i + 2 . On remarque que le fils d'un noeud i a pour pere i.
On dit qu'un tableau ou une liste est un tas si l'objet contenu dans le noeud i est 
toujours plus grand que  les objet contenus dans les noeuds fils (si 
ceux-ci existent).
Dans un tas, le plus grand objet se trouve a la racine, c'est-a-dire
dans le noeud 0.
Il s'agit ici de gerer une liste qui se comporte comme un tas.*/
public class Tas<E extends Ordonnable> extends ArrayList<E> {
   static final long serialVersionUID = 1;
   public void ajouter(E obj) {
	int indice = size();;
	int indiceMoitie;

	add(obj);
	indiceMoitie = (indice - 1)/2;
	while ((indice > 0) && (obj.plusGrand(get(indiceMoitie)))) {
	    set(indice, get(indiceMoitie));
	    indice = indiceMoitie;
	    indiceMoitie = (indiceMoitie - 1) / 2;
	}
	set(indice, obj);
  }
  
  public E retirer() {
      int nbDonnees = size();
      if (nbDonnees == 0) return null;
      
      int indice, indiceDouble, indiceGrand;
      E objetRetire = get(0);
      E deplace = get(nbDonnees-1);
      
      indice = 0;
      indiceDouble = 1;
      
      while(indiceDouble < nbDonnees - 1) {
	  indiceGrand = indiceDouble;
	  if ((indiceDouble < nbDonnees - 2) &&
	      (get(indiceDouble + 1).plusGrand(get(indiceDouble))))
	      indiceGrand = indiceDouble + 1;
	  if (get(indiceGrand).plusGrand(deplace)) {
	      set(indice, get(indiceGrand));
	      indice = indiceGrand;
	      indiceDouble = 2 * indice + 1;
	  }
	  else indiceDouble = nbDonnees;
      }
      set(indice, deplace);
      remove(nbDonnees - 1);
      return objetRetire;
  }
  
  public void afficher() {
      for (E o : this) System.out.print(o + "\n");
      System.out.println();
  }
}