import java.io.*;
import java.util.List;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.Iterator;

/**
 * Algorithmen, WS07/08 Daniel Huson und Regula Rupp
 *
 * Uebungsaufgabe HeapSort
 */
public class HeapSort {
    static String AUTHOR="YOUR_NAME_HERE_PLEASE";

    /**
     * sort an array using heap-sort
     * @param A
     */
    public void sort (int[] A)
    {
	// bitte implementieren
   }

	// dazu bitte folgende Methoden implementieren und benutzen:

	// maxHeapify ...

	// buildMaxHeap ...

	// leftChild...

	// rightChild...

	// swap...

	// getLength...

    // ========= ab hier bitte nichts aendern ============

    /**
     * run the sort program. Usage:  java HeapSort [inputfile [outputfile]]
     * Integers are read until end-of-file or a line starting with '.' is encountered
     * @param args
     * @throws IOException
     */
    public static void main (String[] args) throws IOException {
        System.err.println("HeapSort by "+AUTHOR);
        System.err.println("Either supply names of in- and output file on command line or type values and end by a '.'");
        // setup input and output streams, either from files or from the console
       BufferedReader r=new BufferedReader(args.length>=1?new FileReader(new File(args[0])):new InputStreamReader(System.in));
       BufferedWriter w=new BufferedWriter(args.length>=2?new FileWriter(new File(args[1])):new OutputStreamWriter(System.out));

        // readinput data
        int[] A=readInput(r);

        HeapSort heapSort=new HeapSort();
        heapSort.sort(A);

        // write output data
        writeOutput(w,A);
    }

    /**
     * read the input
     * @param r
     * @return array of numbers indexed 1..n
     * @throws IOException
     */
    private static int[] readInput (BufferedReader r) throws IOException {
        String aLine;
          List input=new LinkedList();
        boolean done=false;
          while((aLine=r.readLine())!=null)
          {
             if(aLine.length()==0)
                continue;
              for(StringTokenizer st=new StringTokenizer(aLine);st.hasMoreTokens();)
              {
                  String token=st.nextToken();
                  if(token.equals("."))
                  {
                       done=true;
                      break;
                  }
                  int x=Integer.parseInt(token);
                  input.add(new Integer(x));
              }
              if(done)
                break;
          }

          int[] A=new int[input.size()+1];
          int i=1;
          for(Iterator it=input.iterator();it.hasNext();)
          {
              A[i++]=((Integer)it.next()).intValue();
          }
        return A;
    }

    /**
     * write the output
     * @param w
     * @param A
     * @throws IOException
     */
    private static void writeOutput (BufferedWriter w,int[] A) throws IOException {
        for(int i=1;i<=getLength(A);i++)
            w.write(" "+A[i]);
        w.write("\n");
        w.flush();
    }
}