// ------------------------------------------------------------
// Sorters -- collection of array sorting algorithms.
//
// File Revision Date: 11/20/02
// ------------------------------------------------------------ 

public class Sorters {

	public static void heapSort (Comparable [] array, int nvals) {

		// Phase 1 -- rearrange the entire array into a "heap"
		
  		for (int n = (nvals - 2) / 2; n >= 0; n--)
		    adjust (array, n, nvals);

		// Phase 2 -- repeatedly switch first and last components,
		// effectively decrement size of array, and re-adjust
		// to a heap...
		
  		for (int n = nvals - 1; n > 0; n--) {
    		Comparable temp = array [0];
		    array [0] = array [n];
    		array [n] = temp;

    		adjust (array, 0, n);
  		}
	}

	// --------------------------------------------------------
	// adjust -- Private method used by heapSort."Adjusts"
	// the binary subtree whose root is at index i, and whose
	// left and right subtrees are already heaps, so that
	// the entire tree is a heap. Parameter nvals gives
	// the effective number of nodes in the tree.

	private static void adjust (Comparable array[], int i, int nvals) {
  		Comparable temp = array [i];

  		int j = 2 * i + 1;  // Start j at root of left subtree of node i
  		boolean done = false;  // Set flag when final replacement position found

  		while (j < nvals && !done)
  		{
    		// Now check if there is a right subtree -- if so, move j
    		// to the max of the left and right children

    		if (j < nvals - 1)
      			if (array[j].compareTo (array[j+1]) < 0)
        			j++;

			// If the value copied from the root node i is >= the value
			// at node j, final replacement position has been found.
			// Otherwise, overwrite data in parent of j with value in j,
			// and descend 1 level deeper in the tree...
       
			if (temp.compareTo (array[j]) >= 0)
				done = true;
			else {
				array [(j-1)/2] = array [j];
				j = 2 * j + 1;           // Try left child first...
			}
		}

		// Final step: copy temp value into parent of j

		array [(j-1)/2] = temp;
	}
}