Chapter 6 - Heap Java

Note that for compatibility with the text use of arrays starting at index 1, array index 0 is not used.

public class Heap {
    static int heapsize;
    public static void main(String a[]) {
           int A[] = {0,4,1,3,2,16,9,10,14,8,7};
           heapsize=A.length-1;
           Build_Max_Heap(A);
           print(A);
    }
 
     static void print(int A[]) {      
           for (int i=1; i<=A.length-1; i++) System.out.print(A[i]+" ");
               System.out.println();
     }
 
     static int parent(int i) { return i/2; }
     static int left( int i ) { return 2*i; }
     static int right( int i ) { return 2*i+1; }
 
     static void exchange(int A[], int i, int j) {
              int t = A[i];
              A[i]=A[j];
              A[j]=t;
      }
 
//@ pre A != null;
//@ post (\forall int j; 1<=j && j < A.length; A[ j ] >= A[left( j )] && A[ j ] >= A[right( j )]);
 
      static void Build_Max_Heap(int A[]) {
              heapsize=A.length-1;
              /*@ loop_invariant
                         (\forall int j; i<j && j<=A.length;
                                 A[ j ] >= A[left( j )] && A[ j ] >= A[right( j )]);
             @*/
             for(int i=heapsize/2; i>=1; i--) Max_Heapify(A, i);
        }
 
//          Recursive
      static void Max_Heapify(int A[], int i) {
            int l = left(i);
            int r = right(i);
            int largest = i; 
            if( l <= heapsize && A[l] > A[i]) largest = l;
            if( r <= heapsize && A[r] > A[largest]) largest = r;
            if( largest != i ) {
                   exchange(A, i, largest);
                   Max_Heapify(A, largest );
             }
        }
}