title: Sorting an array using max-heap in Java
body: <p>I'm working on a program which sorts an array by dividing it into smaller max-heaps and extracting the max-integer out of each one, then deleting it from the heap and running again until every heap is empty, but I can't seem to figure it out. </p>
  
  <p>From where I stand the code looks good, but I don't get the results which I am looking for. My input is created randomly, and makes an array of 512 integers. Here is what it prints for one example run -</p>
  
  <pre><code>Original Array  -391 176 -380 -262 -474 327 -496 214 475 -255 50 -351 179 -385 -442 -227 465 127 -293 288
  Sorted Array 475 465 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 
  n = 20 k = 2
  The number of comparisons is 243
  </code></pre>
  
  <p>Can anyone spot what's wrong with my code? I will be really gladful.</p>
  
  <p><strong>(1) Main Program</strong></p>
  
  <pre><code> import java.io.File;
   import java.util.*;
   import java.io.FileNotFoundException;
   import java.util.Scanner;
   import java.io.IOException;
  
   public class Project {
      static final int n = 20;
      static final int k = 2;
      static int counter = 0;
      private static Scanner scan;
  
      public static void main(String[] args) throws IOException {
          // Optional  - reading from a file containing 512 integers.
          InputCreator.main();
          File f = new File("random.txt");
          // File f = new File("increase.txt");
          // File f = new File("decrease.txt");
          try { scan = new Scanner(f);
          } catch (FileNotFoundException e) {
              // TODO Auto-generated catch block
              e.printStackTrace(); }
          int [] L = new int[n];
          System.out.print("Original Array ");
          for (int i = 0; i &lt; n ; i++)
              { counter++; L[i] = scan.nextInt(); System.out.print(" " + L[i]); }
          Projectsort(L);
      }
  
      private static void Projectsort(int [] L) {
          // int [][] Li = new int [k] [n-(n/k*(k-1))]; // The size of the rest of the integers (n-(n/k*(k-1)) will always be bigger than n/k
          int [] temp = new int [n/k], extra = new int [n-(n/k)*(k-1)];
          int extraIndex = 0, max, maxIndex = 0, r = 0;
          ProjectMaxHeap [] Li = new ProjectMaxHeap [k];
          // The following loop's time effiency is O(k) * O(N/k) = O(N)
          for (int i=0; i&lt;k-1; i++) { counter++; // copying all the integers from Array L into K-1 smaller arrays
              for (int j=0; j&lt;n/k ; j++)
                   { counter++; temp [j] = L[i*(n/k)+j]; }
              Li[i] = new ProjectMaxHeap (temp); }
  
          for (int i=(n/k)*(k-1) ; i&lt;n ; ++i) // The rest of the integers on array L
              { counter++; extra [extraIndex] = L[i]; extraIndex++; }
          Li[k-1] = new ProjectMaxHeap(extra);
          System.out.print("\nSorted Array ");
          for (int i = n ; i &gt; 0 ; i--) { counter++;
              r = 0;
              do{max = Li[r].extractMax(); r++; }while(Li[r].isEmpty() &amp;&amp; r &lt; k - 1);
              for (int j = r; j &lt; k; j++) // Time efficiency O(k)*O(N/k)
              { counter++;
                if(!Li[j].isEmpty()) {
                  if (Li[j].extractMax() &gt; max) { 
                      counter++;
                      max = Li[j].extractMax(); 
                      maxIndex = j; } 
              } 
          System.out.print(max + " ");
          Li[maxIndex].deleteMax(); } }
          System.out.println("\nn = " + n + " k = " + k +"\nThe number of comparisons is " + counter);
      }
   }
  </code></pre>
  
  <p><strong>(2) Max Heap Class</strong></p>
  
  <pre><code>    public class ProjectMaxHeap
  {
      private int [] _Heap;
      private int _size;
  
      public ProjectMaxHeap (int [] A){
          _size = A.length;
          _Heap = new int[A.length]; 
          System.arraycopy(A, 0, _Heap, 0, A.length);
          for (int i = _size / 2 ; i &gt;=0 ; i--) {
              Project.counter++;
              maxHeapify(i); }
      }
  
      private int parent(int pos) 
      { return pos / 2; }
  
      private int leftChild(int pos)
      { return (2 * pos); }
  
      private int rightChild(int pos)
      { return (2 * pos) + 1; }
  
      private void swap(int fpos,int spos) {
          int tmp;
          tmp = _Heap[fpos];
          _Heap[fpos] = _Heap[spos];
          _Heap[spos] = tmp; }
  
      private void maxHeapify (int i) {
          int l = leftChild(i), r = rightChild(i), largest;
          if(l &lt; _size &amp;&amp; _Heap[l] &gt; _Heap[i]) {
              Project.counter+=2;
              largest = l; }
              else largest = i;
          if(r &lt; _size &amp;&amp; _Heap[r] &gt; _Heap[largest]) {
              largest = r;
              Project.counter+=2; }
          if (largest != i) {
              Project.counter++;
              swap(i, largest);
              maxHeapify (largest); }
          } 
  
      protected boolean isEmpty() { return _size == 0; }
  
      protected void deleteMax() {
          if (_size &gt; 1) {
              Project.counter++;
              maxHeapify(0);
              int max = _Heap[0];
              _size--;
              swap(0, _size);
              maxHeapify(0); }
          else _size = 0;    
      }
  
      protected int extractMax() {
          maxHeapify(0);
          return _Heap[0];
      }
  }
  </code></pre>
  
  <p><strong>(3) Input Creator</strong></p>
  
  <pre><code>import java.io.BufferedWriter;
  import java.io.File;
  import java.io.FileWriter;
  import java.io.IOException;
  import java.util.*;
  import java.io.FileReader;
  import java.io.BufferedReader;
  
  public class InputCreator {
      public static void main() {
          randomizer();
          decrease();
          increase();
      }
      private static void randomizer() {
          // The target file
          File out = new File("random.txt");
          FileWriter fw = null;
          int n = 0;
          // Try block: Most stream operations may throw IO exception
          try {
              // Create file writer object
              fw = new FileWriter(out);
              // Wrap thק writer with buffered streams
              BufferedWriter writer = new BufferedWriter(fw);
              int line;
              Random random = new Random();
              while (n &lt; Project.n) {
                  // Randomize an integer and write it to the output file
                  line = random.nextInt(1000)-500;
                  writer.write(line + "\r\n");
                  n++;
              }
              // Close the stream
              writer.close();
          } catch (IOException e) {
              e.printStackTrace();
              System.exit(0);
          }
      }
      private static void increase() {
          // The target file
          File out = new File("increase.txt");
          FileWriter fw = null;
          int n = 0;
          int temp = 0;
          // Try block: Most stream operations may throw IO exception
          try {
              // Create file writer object
              fw = new FileWriter(out);
              // Wrap thק writer with buffered streams
              BufferedWriter writer = new BufferedWriter(fw);
              int line;
              Random random = new Random();
              while (n &lt; Project.n) {
                  // Randomize an integer and write it to the output file
                  line = random.nextInt((n+1)*10);
                  if(line &gt; temp) {
                  writer.write(line + "\r\n");
                  n++; 
                  temp = line; }
              }
              // Close the stream
              writer.close();
          } catch (IOException e) {
              e.printStackTrace();
              System.exit(0);
          }
      }
          private static void decrease() {
          // The target file
          File out = new File("decrease.txt");
          FileWriter fw = null;
          int n = 0;
          int temp = 10000;
          // Try block: Most stream operations may throw IO exception
          try {
              // Create file writer object
              fw = new FileWriter(out);
              // Wrap thק writer with buffered streams
              BufferedWriter writer = new BufferedWriter(fw);
              int line;
              Random random = new Random();
              while (n &lt; Project.n) {
                  // Randomize an integer and write it to the output file
                  line = 10000 - random.nextInt((n+1)*20);
                  if(line &lt; temp) {
                  writer.write(line + "\r\n");
                  n++; 
                  temp = line; }
              }
              // Close the stream
              writer.close();
          } catch (IOException e) {
              e.printStackTrace();
              System.exit(0);
          }
      }
  }
  </code></pre>