/*
 * HeapSort.java
 *
 */

import java.util.Random;
import java.util.Date;
import net.datastructures.HeapPriorityQueue;
import net.datastructures.Entry;

public class HeapSort {
    
   final static int DEFAULT_ELEMENT_NUM=30000; 
    
   public static void main (String[] args) {
      int i, j, tmp;
      int[] a;

      int n;  /* the number of elements in the array */ 
      if (args.length == 0)
          n = DEFAULT_ELEMENT_NUM;
      else
          n = Integer.parseInt(args[0]);
      a = new int[n];       


      /* set the initial value randomly for the ARRAY */
      Random r = new Random();
      for (i=0; i< a.length; i++) {
        a[i] =  r.nextInt(n);
      }
      
       /* create an empty heap */
      MyComparator c = new MyComparator();
      HeapPriorityQueue h = new HeapPriorityQueue(c);
      
      /* get the starting time */
      Date start = new Date();
      
      /* heap sort */
      for (i=0;i<a.length;i++) {
        h.insert(a[i],a[i]);
      }
      i = 0;
      while (  !(h.isEmpty()) ) {
        Entry e = h.removeMin();
        a[i] = ((Integer)e.key()).intValue();
        i++;
      }
      
      /*get the ending time */
      Date end = new Date();
      System.out.println("The running time is "+ (end.getTime()-start.getTime()) + " milliseconds");
      
      /* here we only select 10 elements in sorted array to print*/
      for (i=0; i < a.length; i+= a.length/10) {
          System.out.print(a[i] +" ");
      }  
      System.out.println();
  }
}