// Heapsort.java: sorts A[1],...,A[A.length-1]
public class Heapsort {

   private int parent(int i) { return i/2; }
   private int left  (int i) { return 2*i; }
   private int right (int i) { return 2*i + 1; }
   private int heapsize; // how much of array "counts"

   private void exchange(double[] A, int i,
         int largest) {
      double temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
   }

   private void maxHeapify(double[] A, int i) {
      int l = left(i);
      int r = right(i);
      int largest;
      if (l <= heapsize && A[l] > A[i]) largest = l;
      else largest = i;
      if (r <= heapsize && A[r] > A[largest])
            largest = r;
      if (largest != i) {
         exchange(A, i, largest); 
         maxHeapify(A, largest);
      }
   }

   private void buildMaxHeap(double[] A) {
      heapsize = A.length - 1;
      for (int i = heapsize/2; i >= 1; i--)
         maxHeapify(A, i);
   } 

   public void printheap(double[] A) {
      System.out.print("heapsize:" + heapsize + "--");
      for (int i = 1; i <= A.length - 1; i++) {
         System.out.print(A[i] + ", ");
      }
      System.out.println();
   }
      
   public void heapsort(double[] A) {
      buildMaxHeap(A);
      for(int i = A.length -1; i >= 2; i--) {
         exchange(A, 1, i);
         heapsize--;
         maxHeapify(A, 1);
      }
   }

   public boolean isSorted(double[] A) {
      for (int i = 1; i < A.length - 1; i++)
         if (A[i] >= A[i+1]) return false;
      return true;
   }
}

// HeapsortTest.java: sort array of random #s
import java.util.*;
public class HeapsortTest {
   private double[] A;
   private Heapsort heap;
   private Random r;
   private int size;

   public HeapsortTest(int s) {
      size = s;
      A = new double[size];
      heap = new Heapsort();
      r = new Random(31415);
   }

   public void randomTest() {
      long startTime;
      startTime =  System.currentTimeMillis();
      for (int i = 1; i < size; i++)
         A[i] = r.nextDouble();
      // heap.printheap(A);
      elapsedTime(startTime, "Time to generate, ");

      startTime =  System.currentTimeMillis();
      heap.heapsort(A);
      // heap.printheap(A);
      elapsedTime(startTime, "Time to sort, ");
      System.out.println("isSorted: " +
         heap.isSorted(A));
   }

   public static void elapsedTime(long startTime,
         String s) {
      long stopTime = System.currentTimeMillis();
      double elapsedTime =
         ((double)(stopTime - startTime))/1000.0;
      System.out.println(s + "elapsed time: " +
         elapsedTime + " seconds");
   }

   public static void main(String[] args) {
      final int SIZE = 5000000;
      HeapsortTest h = new HeapsortTest(SIZE);
      h.randomTest();
   }
}

Test of textbook's data:
index:    1    2    3   4    5   6    7    8    9    10
-------------------------------------------------------
size:10| 4.0, 1.0, 3.0,2.0,16.0,9.0,10.0,14.0, 8.0, 7.0
size:10|16.0,14.0,10.0,8.0, 7.0,9.0, 3.0, 2.0, 4.0, 1.0
size: 9|14.0, 8.0,10.0,4.0, 7.0,9.0, 3.0, 2.0, 1.0,16.0
size: 8|10.0, 8.0, 9.0,4.0, 7.0,1.0, 3.0, 2.0,14.0,16.0
size: 7| 9.0, 8.0, 3.0,4.0, 7.0,1.0, 2.0,10.0,14.0,16.0
size: 6| 8.0, 7.0, 3.0,4.0, 2.0,1.0, 9.0,10.0,14.0,16.0
size: 5| 7.0, 4.0, 3.0,1.0, 2.0,8.0, 9.0,10.0,14.0,16.0
size: 4| 4.0, 2.0, 3.0,1.0, 7.0,8.0, 9.0,10.0,14.0,16.0
size: 3| 3.0, 2.0, 1.0,4.0, 7.0,8.0, 9.0,10.0,14.0,16.0
size: 2| 2.0, 1.0, 3.0,4.0, 7.0,8.0, 9.0,10.0,14.0,16.0
size: 1| 1.0, 2.0, 3.0,4.0, 7.0,8.0, 9.0,10.0,14.0,16.0

Typical output (sucsessful searchs):
Sort  100000 doubles:
Time to generate, elapsed time: 0.033 seconds
Time to sort, elapsed time: 0.082 seconds
isSorted: true
Sort  500000 doubles:
Time to generate, elapsed time: 0.139 seconds
Time to sort, elapsed time: 0.544 seconds
isSorted: true
Sort 1000000 doubles:
Time to generate, elapsed time: 0.268 seconds
Time to sort, elapsed time: 1.271 seconds
isSorted: true
Sort 5000000 doubles:
Time to generate, elapsed time: 1.339 seconds
Time to sort, elapsed time: 8.331 seconds
isSorted: true