/*
 * @(#)HeapSortAlgorithm.java      1.0 99/09/19
 *
 * Sorry.
 * This code has not copy right. It was just hacked together from what I
 * recalled from Algorithms class:
 * 
 * Think of the list as a binary tree, position i has the sons 
 *    2*(i+1)-1 and 2*(i+1)
 *
 * The heap-property: the value of every sun is smaller than the value
 *                    of its father node
 *
 * The heap sort algorithm:
 *   Phase 1: Establish the heap-property (bottom up)
 *   Phase 2: while not done, swap the root (cotaining the maximal element)
 *            with the last element of the heap and reduce heap size;
 *            than re-establish the heap property.
 *
 */

/**
 * A heap sort demonstration algorithm
 * SortAlgorithm.java
 *
 * @author Oliver M"oller (well, just of this code, not of the algorithm...)
 * @version     @(#)HeapSortAlgorithm.java 1.0, 19 September 1999
 */

public class HeapSortAlgorithm extends SortAlgorithm {


   private int upperBound;

   private void swap(int a[], int i, int j){
      int T;
      T = a[i]; 
      a[i] = a[j];
      a[j] = T;
   }
   private void Heapify(int a[], int i) throws Exception {
       int j=(2*(i+1))-1;
       int k=(2*(i+1));
       
       if(j <= upperBound){
	   if( (k > upperBound) && (j == upperBound)){
	       ncmp_count++;
	       if(a[i] < a[j]){
		   swap(a,i,j);		   
		   Heapify(a,j);
		   pause(i,upperBound);}}
	   else {// both are legal
	       ncmp_count++;
	       if(a[j] > a[k]){
		   ncmp_count++;
		   if(a[i] < a[j]){
		       swap(a,i,j);
		       Heapify(a,j);
		       pause(i,upperBound);}}

	       else {// we know: a[k] >= a[j]
		   ncmp_count++;
		   if(a[i] < a[k]){
		   swap(a,i,k);
		   Heapify(a,k);
		   pause(k,upperBound);}}}
       }
   }


    public void sort(int a[]) throws Exception {
	upperBound = a.length -1;

	// Phase 1:
	for(int i = upperBound/2 ; i >= 0; i--){
	    if(stopRequested)return;
	    Heapify(a,i);
	}
	// Phase 2:
	while(upperBound > 0){
	    if(stopRequested)return;
	    swap(a,0,upperBound);
	    upperBound--;
	    Heapify(a,0);
	    pause(0,upperBound);
	}
	finished = true;
	pause();
    }
}