import java.io.*;
import java.lang.*;
import java.util.*;

public class TriTas  {
	
  final static int N = 10;

  static int[] a = new int[N];
  static int   nTas = 0;

  static void Ajouter (int v)  {
  // \esc{Ajouter a` un tas, voir page \pageref{prog:ajouter-tas}}

    int    i;

    ++nTas;
    i = nTas - 1;
    while (i > 0 && a [(i - 1)/2] <= v) {
        a[i] = a[(i - 1)/2]; 
        i = (i - 1)/2;
    }
    a[i] = v;
  }

  static int Maximum ()  {
  // \esc{Maximum d'un tas, voir page \pageref{prog:maximum-tas}} */

    return a[0];
  }

  static void Supprimer () {
  // \esc{Supprimer dans un tas, voir page \pageref{prog:supprimer-tas}} */

    int i, j;
    int v;

    a[0] = a[nTas - 1];
    --nTas;
    i = 0; v = a[0];
    while (2*i + 1 < nTas) {
        j = 2*i + 1;
        if (j + 1 < nTas) 
            if (a[j + 1] > a[j]) 
                ++j;
        if (v >= a[j]) 
            break;
        a[i] = a[j]; i = j;
    }
    a[i] = v;
  }

  static void HeapSort ()  {
  // \esc{{\em HeapSort}, voir page \pageref{prog:heapsort}}

    int      i;
    int      v;

    nTas = 0;
    for (i = 0; i < N; ++i) {
        Ajouter (a[i]);
        Impression();
    }
    for (i = N - 1; i >= 0; --i) { 
        v = Maximum();
        Supprimer();
        a[i] = v;
       Impression();
     }
  }

  static void Initialisation() {
      for (int i = 0; i < N; ++i)
          a[i] = (int) (Math.random() * 128);
  }

  static void Impression() {
      for (int i = 0; i < N; ++i)
          System.out.print (" " + a[i] + " ");
      System.out.println ("");
  }

  public static void main(String args[]) {

      Initialisation();   // \esc{On lit le tableau}
      Impression();       // \esc{et on l'imprime}
      HeapSort();         // \esc{On trie}
      Impression();       // \esc{On imprime le résultat} 
  }
}