1/*2 * HeapSort.java3 *4 * Computer Science S-22, Harvard University5 */6 7/**8 * HeapSort - a class containing an implementation of the heapsort9 * algorithm. 10 */11public class HeapSort {12 public static final int NUM_ELEMENTS = 10;13 14 /** heapSort */15 public static <T extends Comparable<T>> void heapSort (T[] arr) {16 // Turn the array into a max-at-top heap.17 // Note that this does *not* create an extra copy of the array.18 // The heap object simply holds a reference to the original array, 19 // with the elements rearranged as needed.20 Heap<T> heap = new Heap<T>(arr);21 22 // Repeatedly put elements in their correct positions.23 int endUnsorted = arr.length - 1;24 while (endUnsorted > 0) {25 //26 // Get the largest remaining element and put it where it27 // belongs -- at the end of the portion of the array that28 // is still unsorted.29 //30 T largestRemaining = heap.remove();31 arr[endUnsorted] = largestRemaining;32 33 endUnsorted--;34 }35 }36 37 public static void printArray(Object[] arr) {38 System.out.print("{ ");39 40 for (int i = 0; i < arr.length; i++) {41 System.out.print(arr[i] + " ");42 }43 44 System.out.println("}");45 }46 47 public static void main(String[] args) { 48 Integer[] arr = new Integer[NUM_ELEMENTS];49 for (int i = 0; i < NUM_ELEMENTS; i++) {50 arr[i] = (int)(50 * Math.random());51 }52 printArray(arr);53 54 heapSort(arr);55 System.out.print("heap sort:\t");56 printArray(arr);57 }58}