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

public class Heapsort
{
  static int laenge;
  static int[] unsort;


  static int eingabe()
   {     
     while (laenge<=0)
       {
	 try
	   {
	     BufferedReader Input = new BufferedReader(
						       new InputStreamReader(System.in));
	     System.out.print("Bitte n eingeben: ");
	     laenge = Integer.parseInt(Input.readLine());
	   }
	 catch (Exception e)
	   {
                       System.out.println("Fehler in Eingabe(): "+e);
	   }
       }
     return laenge;
   }

  static void ausgabe()
   {
     
     for (int i=0; i<laenge; i++)
       {
	 System.out.print(unsort[i] + ", ");
       }
     System.out.print("\n");
   }


  static void init()
   {
     unsort = new int[laenge];
     Random rand = new Random(26);
     for (int i=0; i<laenge; i++)
       {
	 unsort[i] = (rand.nextInt() % 4793) - 2396;
       }
   }

  static void downheap (int[] a, int v, int n)
   {
     int w=2*v+1;                 // erster Nachfolger von v
     while (w<n)
       {
	 if (w+1<n)               // gibt es einen zweiten Nachfolger?
	   if (a[w+1]>a[w]) w++;
	 // w ist Nachfolger von v mit maximum Label
	 
	 if (a[v]>=a[w]) return;  // v hat Heapeigenschaft
	 // sonst
	 exchange(a, v, w);      
	 v=w; w=2*v+1;           
       }
   }
  
  
  static void buildheap (int[] a, int n)
   {
     for (int v=n/2-1; v>=0; v--)
       downheap (a, v, n);
   }
  
  
  static void exchange (int[] a, int i, int j)
   {
     int h=a[i];
     a[i]=a[j];
     a[j]=h;
   }
  
  static int holedownheap (int[] a, int n)
   {
     int v=0, w=2*v+1;
     while (w+1<n)     // zweiter Nachfolger existiert
       {
	 if (a[w+1]>a[w]) 
	   w++;
	 
	 a[v]=a[w];
	 v=w; w=2*v+1;
       }
     if (w<n)    // ein Blatt
       {
	 a[v]=a[w];
	 v=w;
       }
     // die Luecke hat das Blatt erreicht, es wird zurueckgegeben
     return v;
   }
  
  
  
  
  



  static void upheap (int a[], int v, int x)
   {
     int u;
     a[v]=x;
     while (v>0)
       {
	 u=(v-1)/2;    // Vorgaenger
	 if (a[u]>=a[v]) return;
        // sonst
	 exchange(a, u, v);
	 v=u;
       }
   }
  
  
  
  
  
  
  
  
  static void bottomupHeapsort (int a[], int n)
   {
     int x, u, v;
     buildheap(a, n);
     for (v=n-1; v>0; v--)
       {
        x=a[v];    //Label des letzten Blatts
        a[v]=a[0];
        u=holedownheap(a, v);
        upheap (a, u, x);
       }
   }
  
  
  public static void main(String argv[])
    {
       int n;
       n = eingabe();
       init();
       System.out.println("Array vor dem Sortieren: ");
       ausgabe();
       bottomupHeapsort(unsort,n);
       System.out.println("Array nach dem Sortieren: ");
       ausgabe();

    }  

}