class HeapSort {
 
  static int heapSize; 

  static void heapify(int A[], int i) {
    int left = ... 
    int right = ...
    int largest; 
    if () 
      largest = ... ;
    else ... ; 
    if ( ... ) 
      largest = ... ;
    if (largest != i) {
      int tmp = A[i];
      A[i] = A[largest];
      A[largest] = tmp;
      heapify(A,largest);
    }
  }

  static void buildHeap(int A[]) {
    heapSize = A.length-1; 
    for (int i = ... ; ... ; i--)
      ...
  }

  static void heapSort(int A[]) {
    ...
    }   
  }

  static void printArray(String text, int A[]) {
    System.out.print(text);
    System.out.print(" is: ");
      for (int i = 0; i < A.length; i++)
        System.out.print(A[i]+ " ");
    System.out.println();
  }

  static void printHeap(String text, int A[]) {
    System.out.print(text);
    System.out.print(" is: ");
    for (int i = 0; i < A.length; i++)
      System.out.print(A[i]+ " ");
    System.out.println(" after calling buildHeap");
  }

  static void printSortedArray(String text, int A[]) {
    System.out.print(text);
    System.out.print(" is: ");
    for (int i = 0; i < A.length; i++)
      System.out.print(A[i]+ " ");
    System.out.println(" after calling sortHeap");
  }


  public static void main (String args[]) {
    
    long t; 

    int A[] = {31, 41, 59, 26, 41, 58, 11}; 

    printArray("A",A);
    buildHeap(A);
    printHeap("A",A);    

    int B[] = {31, 41, 59, 26, 41, 58, 11}; 

    printArray("B",B);
    t= System.currentTimeMillis();   
    heapSort(B);
    t= System.currentTimeMillis()-t;
    System.out.println("T= "+t);

    printSortedArray("B",B);
   
  }
}