/*
 * HeapSort2Algorithm.java	3.1 2000/02/15  Koji YAMAMOTO
 *
 * Copyright (c) 2000 Science University of Tokyo. All Rights Reserved.
 *
 */

class HeapSort2Algorithm extends SortAlgorithm {

   int INT_MAX = 60000;   
   int N;
  
   void upheap(int k,int a[])throws Exception  {
      int v;
      v = a[k];            //v is inserted number
      a[0] = INT_MAX;      
      while(a[k/2] <= v) { 
         a[k] = a[k/2];
         k = k/2;
         pause();
      }
      a[k] = v;
   }

   void downheap(int k,int a[])throws Exception  {
      int j, v;
      v = a[k];
      while(k <= N/2) {
         j = k+k;
         if (j<N && a[j] < a[j+1]) j++;
         if (v >= a[j]) break;
         a[k] = a[j]; k = j;
         pause();
     }
     a[k] = v;
   }

   int remove(int a[])throws Exception  {
      int v = a[1]; 
      a[1] = a[N];
      N--;
      downheap(1,a);
      return v;
   } 

   void sort(int a[]) throws Exception {
      N = a.length-1;
      for (int k=1;k<=N;k++) {
         upheap(k,a);
         pause();
          }
      for (int k=N;k>=1;k--) {
         a[k] = remove(a);  
         pause(k);
           }
   pause();
   }
}