/*
 * @(#)HSortAlgorithm.java	1.0 96/02/18 Istvan Simon
 *
 * Copyright (c) 1996 Istvan Simon & California State University, Hayward
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
 * without fee is hereby granted, provided this copyright notice
 * is displayed, and provided that user accepts all risks of 
 * of using or running this software and agrees that author
 * of software and California State University Hayward shall
 * not be held liable for any claims due to the use of this software
 * for any purpose whatsoever. 
 * 
 * Software is intended to be used only as a demonstration program. 
 */

/**
 * Heap Sort Demonstration algorithm
 *
 * @author Istvan Simon
 * @version 	1.0, 18 Feb 96
 *
 * 	
 */

class HSortAlgorithm extends SortAlgorithm {

    int n;      // number of elements in array. 
		// Initialized when sort is invoked

    int lo,hi;  // low and high water marks bracket part of array where heap 
		// property holds. Initialized when sort invoked

    // index of father of a node in Heap. -1 if NIL
    int father(int i) { return ( i>0 ?  (i-1)/2 :  -1) ; }  
									
    // index of left child of node in Heap. -1 if NIL
    int left(int i) { return ((2*i + 1) <= hi ?  (2*i + 1):  -1) ; } 	

    // index of right child of node in Heap 						  		
    int right(int i) { return ((2*i+2) <= hi ?  (2*i+2) :  -1) ; }
	
    // return index of larger node. i is a left child j is right child or NIL. 
    // May return -1 if called with both NIL.
    int maxchild ( int i, int j, int a[]) throws Exception {
	pause();
	if ( j >= 0)  return ( a[i] > a[j] ? i : j);
	else return i;
    }

    // sink node i to its proper place in the maxheap
    void sinknode(int i, int a[]) throws Exception {
	
	int mc  = maxchild(left(i),right(i), a);
	int t = a[i]; 

	while ((mc != -1) && ( t < a[mc])) {

		// sink further
		a[i] = a[mc];
		a[mc] = t;
		i=mc;

		pause();
		mc = maxchild(left(i),right(i), a);
	}
    }		

		

    
    void sort(int a[]) throws Exception {
	n = a.length;
	lo = father(n-1) + 1;
	hi = n-1;



	// Construct maxheap

	while (lo > 0) {

		lo--;
		pause(lo,hi);

		sinknode(lo,a);

	}

	while (hi > 0) {
		int t=a[hi];
		a[hi] = a[0];
		a[lo]=t;
		hi--;
		pause(lo,hi);
		sinknode(lo,a);
	}
    }

     
}