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   }