/**
    FILE:           HeapSort.java
    AUTHOR:         Cheng, Jeff
    LAST CHANGE:    3-22-02
    Functions:      HeapSort()--------> creates an array, may be presorted.
                    createAndSort()--> creates an array and sorts the
                                       array, may print array after.
                    heapify()--------> perform bottom-up heap construction
                    print()----------> print the entire array
                    sort()-----------> sort the array using in-place heapsort
                    
    COPYRIGHT:      You may use, modify, or distribute my code for 
                    non-commerical use only; you must cite me, Jeff Cheng, 
                    as the source. 
*/

package sorts;

class HeapSort{
    public static final int MAX_VALUE = 1000000;
    private static int a[];
    //  +1 because we don't use index 0 but still need to use as many
    //  elements as size.
    public HeapSort(int arraySize, boolean presorted){
        a = new int[arraySize + 1];
        
        if (presorted){  //  sorted array
            for (int i=1; i< a.length; i++){
                a[i] = i;
        }
        }
        else{//  seed the array elements randomly
            for (int i=1; i < a.length; i++){
                a[i] = (int)(Math.random()*MAX_VALUE);   
        }
        }
    }
    
    public static void createAndSort(int arraySize, boolean presorted,
                                     boolean printIt){
        long timeBegan = 0;
        long timeFinished = 0; 
        long timeNeeded = 0;
        
        //  create an array of integers
        HeapSort aHeapSorter = new HeapSort(arraySize, presorted);

        //  time the sorting algorithm
        timeBegan = System.currentTimeMillis();
        aHeapSorter.sort();
        timeFinished = System.currentTimeMillis();
        timeNeeded = timeFinished - timeBegan;
        System.out.println("\t Sorting the array of size " + arraySize +
                            " took = " + timeNeeded + " milliseconds.");       
                            
        if (printIt){
            System.out.println("\n\t Now print the array elements:\n" +
                               "\t Note if the array is too large, " +
                               "the elements may run off the screen!\n");
            aHeapSorter.print();
        }
    }
    
  public void print(){
    for (int i = 1; i < a.length;i++){
        System.out.println(" a[" + i + "] = " + a[i] + "\n");
        }
 }
 
 public void heapify(){
    boolean done = false;   //  if we found the right position or at a leave
	int currentParent = 0;
	int child = 0;  //  a node's child, one each at position 2^i and 
	                //  2^i + 1
	int hold = 0;
	int actualSize = a.length-1;
		
	//  i is the floor of n/2, e.g. 7 for size = 15
	//  this is the rightmost, last, internal node.
	//  left child is at 2i and right child at 2i+1
	for (int i = actualSize/2; i >= 1; i--){
	    done = false;   
	    //  assume we are still looking for the right position or still
	    //  at an internal node
        currentParent = i;   //  examining the ith node
     
        while (done == false){
            child = 2 * currentParent;   //  left child's position
            
            if (child <= actualSize){   //  we are still inside the heap
                                        //  because we are not a leave yet
                                        //  because we have at least a child
                if (child + 1 <= actualSize){ //  if a right child exists
                                            //  now find the largest child
                    if (a[child + 1] > a[child]){
                        //  the right child is biggest, which is at
                        //  position child + 1
                        child++;
                    }
                }
            
                if (a[child] > a[currentParent]){    //  if a child is bigger 
                                                    //  than its parent
                                                    //  swap them
                    hold = a[currentParent];
                    a[currentParent] = a[child];
                    a[child] = hold;
                    currentParent = child;  //  the root should be the child,
                                            //  which is bigger in key
                }
                else {  //  a[child] <= a[currentParent]
                    done = true;
                    //  because we have currentParent, the root, >= both kids.

                }
            }
        else {  
            done = true;
            //  because we are outside the heap, at a leave, no kids.
            }   //  end of outer if
        }   //  end of while
    }   //  end of for
    }
    
 public void sort() {
    int heapSize = a.length - 1;
    int hold = 0;
    boolean done = false;
    int currentParent = 1;
    int child = 0;
    
    heapify();  //  using bottom-up construction	

    //  swap a[first] and a[a.length-1]
    hold = a[heapSize]; 
    a[heapSize] = a[1];
    a[1] = hold;
        
    heapSize--; //  now the heap is one node smaller
    
    while (heapSize >= 1){  //  while still elements to sort
        done = false;           
        currentParent = 1;  //  insert at the root
        
        while (done == false){
            child = 2 * currentParent;   //  left child's position
            
            if (child <= heapSize){   //  we are still inside the heap
                                        //  because we are not a leave yet
                                        //  because we have at least a child
                if (child + 1 <= heapSize){ //  if a right child exists
                                            //  now find the largest child
                    if (a[child + 1] > a[child]){
                        //  the right child is biggest, which is at
                        //  position child + 1
                        child++;
                    }
                }
            
                if (a[child] > a[currentParent]){    //  if a child is bigger 
                                                    //  than its parent
                                                    //  swap them
                    hold = a[currentParent];
                    a[currentParent] = a[child];
                    a[child] = hold;
                    currentParent = child;  //  the root should be the child,
                                            //  which is bigger in key
                }
                else {  //  a[child] <= a[currentParent], both children are 
                        //  smaller than the parent
                    done = true;
                    //  because we have currentParent, the root, >= both kids.
                }
            }
        else {  
            done = true;
            //  because we are outside the heap, at a leave, no kids.
            }   //  end of outer if
        }   //  end of inner-while
        
        //  swap a[first] and a[last]
        hold = a[heapSize]; 
        a[heapSize] = a[1];
        a[1] = hold;
        
        heapSize--;
        }   //  end of outer-while
   }  //  end of sort
   
}