/* File MaxHeap.java
 * Author: Wayne Snyder
 * Date: 3/25/14
 * Purpose: This is an example of the MaxHeap algorithm
 *     discussed in the CS 112 lecture on 3/25/14. 
 * Known bugs: This was just a lecture illustration, and does
 *     not account for heap underflow.
 */ 

public class Heap {
   
   private final int SIZE = 10;       // initial length of array
   private int next = 0;              // limit of elements in array
   private int[] A = new int[SIZE];   // implements tree by storing elements in level order
   
   // standard resize to avoid overflow
   
   private void resize() {
      int[] B = new int[A.length*2];
      for(int i = 0; i < A.length; ++i)
         B[i] = A[i];
      A = B; 
   }
   
   // methods to move up and down tree as array
   
   private static int parent(int i) { return (i-1) / 2; }
   private static int lchild(int i) { return 2 * i + 1; }
   private static int rchild(int i) { return 2 * i + 2; }
   
   // standard swap, using indices in array
   
   private void swap(int i, int j) {
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
   }
   
   // basic data structure methods
   
   public boolean isEmpty() {
      return (next == 0);
   }
   
   public int size() {
      return (next);
   }
   
   // insert an integer into array at next available location
   //    and fix any violations of heap property on path up to root
   
   public void insert(int k) {
 
      if(size() == A.length) resize(); 
      A[next++] = k; 
      
      for(int i = next-1; i > 0 && A[i] > A[parent(i)]; i = parent(i)) { 
         swap(i,parent(i));
      }
      
   }
   
   
   public int getMax() {
      --next;
      swap(0,next);                // swap root with last element
      int i = 0; 
      int maxChild = maxChild(0);  
      
      // while there is a maximum child and element out of order, swap with max child
      
      while(maxChild != -1 && A[i] < A[maxChild]) { 
         swap(i,maxChild);
         i = maxChild; 
         maxChild = maxChild(i); 
         
      }
      
      return A[next];
   }

   
   // return index of maximum child of i or -1 if i is a leaf node (no children)
   
   private int maxChild(int i) {
      if(lchild(i) >= next)
         return -1;
      if(rchild(i) >= next)
         return lchild(i);
      else if(A[lchild(i)] > A[rchild(i)])
         return lchild(i);
      else
         return rchild(i); 
   }
   
   // heapsort: if call this while A is being used, will erase everything in A!
   
   public static void heapSort(int[] B) {
      Heap H = new Heap(); 
      for(int i = 0; i < B.length; ++i)
         H.insert(B[i]); 
      for(int i = H.next-1; i >= 0; --i)
         B[i] = H.getMax();
   }
   
   // debug methods
   
   private void printHeap() {
      for(int i = 0; i < next; ++i)
         System.out.print(A[i] + " ");
      System.out.println("\t next = " + next);
   }
   
   private void printHeapAsTree() {
      printHeapTreeHelper(0, ""); 
   }
   
   private void printHeapTreeHelper(int i, String indent) {
      if(i < next) {

         printHeapTreeHelper(rchild(i), indent + "   "); 
                   System.out.println(indent + A[i]);
         printHeapTreeHelper(lchild(i), indent + "   "); 
      }
   }
   

   
 
   
   // Unit Test 

   
   public static void main(String [] args) { 
      Heap H = new Heap(); 
      
      
      
      // test basic methods
      int[] S = { 2, 9, 7, 5  };
      
      for(int i = 0; i < S.length; ++i) {
         H.insert(S[i]);
      }
      

            System.out.println(); 
      H.printHeap(); 
      System.out.println(); 
      H.printHeapAsTree(); 
      H.getMax(); 
            System.out.println(); 
      H.printHeap(); 
      System.out.println(); 
      H.printHeapAsTree(); 
      H.insert(6);
      H.getMax(); 
      H.insert(8);
      System.out.println(); 
      H.printHeap(); 
      System.out.println(); 
      H.printHeapAsTree(); 
      System.out.println(); 
      
      System.out.println(); 
      
      


   }
}