1  /* 
  2   * Java HeapSort
  3   * Author: John Bryan, Jr.
  4   * Date: 09/02/2006 
  5   * Reads integers from file, integers.txt, performs heapsort,
  6   * writes sorted integers to screen and to file, sorted.integers.txt.
  7   */
  8
  9
 10  import java.io.*;
 11  import java.util.*;
 12  import java.lang.*;
 13
 14
 15  public class hs
 16  {
 17      private static int k,i,j,N;
 18
 19      public static int [] ConstructHeap(int []A) throws IOException
 20      {
 21         for (i=N-1; i>=0; i--)
 22            A=Bubbledown(A);
 23         return A;
 24      }
 25
 26
 27      public static void FilePrintArray(int []A) throws IOException
 28      {
 29          BufferedWriter output = new BufferedWriter(
 30                                  new FileWriter("sorted.integers.txt"));
 31          for (int i=0; i<A.length;i++)
 32          {
 33             output.write(" " + A[i]);
 34          }
 35          output.close();
 36      }
 37
 38
 39      public static void HeapSort(int []A) throws IOException
 40      {
 41          for (int r=N-1; r>0; r--)
 42          {
 43             k=r;
 44             j=0;
 45             A=Swap(A);
 46             i=0;
 47             N=r;
 48             A=Bubbledown(A);
 49          }
 50          System.out.println("The sorted integers are  ");
 51          PrintArray(A);
 52          FilePrintArray(A);
 53          return;
 54      }
 55
 56
 57      public static int[] Bubbledown(int []A) throws IOException
 58      {
 59         j=i;
 60         do
 61         {
 62            k=j;
 63            if(((2*k+1)<N)&&(A[2*k+1]>A[j]))
 64               j=2*k+1;
 65            if(((2*k+2)<N)&&(A[2*k+2]>A[j]))
 66               j=2*k+2;
 67            A=Swap(A);
 68         }while(k!=j);
 69         return A;
 70      }
 71
 72
 73      public static int[] Swap(int []A) throws IOException
 74      {
 75         int temp;
 76         temp=A[k];
 77         A[k]=A[j];
 78         A[j]=temp;
 79         return A;
 80      }
 81
 82
 83      public static void PrintArray(int []A) throws IOException
 84      {
 85          for (int i=0; i<A.length;i++)
 86          {
 87             System.out.print(" " + A[i]);
 88          }
 89          System.out.println();
 90      }
 91
 92
 93      public static int FindN() throws IOException
 94      {
 95          String line;
 96          N=0;
 97          BufferedReader in=new BufferedReader(
 98                            new FileReader("integers.txt"));
 99          while((line = in.readLine()) != null)
100          {
101             int value;
102             String[] words = line.split("\\s+");
103             for (int m=0;m<words.length;m++)
104             {
105                N++;
106             }
107           }
108           in.close();
109           return N;
110      }
111
112
113      public static int[] GetIntegers(int[] A) throws IOException
114      {
115          String line;
116          BufferedReader in2 = new BufferedReader(
117                               new FileReader("integers.txt"));
118          int q=0;
119          while((line = in2.readLine()) != null)
120          {
121             int value;
122             String[] words = line.split("\\s+");
123             for (int m=0;m<words.length;m++)
124                {
125                   A[q] = Integer.parseInt(words[m].trim());
126                   q++;
127                }
128          }
129          in2.close();
130          return A;
131      }
132
133
134      public static void main( String[] args ) throws IOException
135      {
136         N=FindN();
137         int[] A = new int[N];
138         A=GetIntegers(A);
139         A= ConstructHeap(A);
140         HeapSort(A);
141         System.exit(0);
142      }
143  }