public class HeapSort
1: import java.util.Scanner;
3: /**
4: * Sorting using heap sort.
5: *
6: * @author Mark Young (A00000000)
7: */
8: public class HeapSort {
10: /**
11: * biggest number in list
12: */
13: private static final int BIGGEST = 1000;
14:
15: /**
16: * keyboard scanner for whole program
17: */
18: private static final Scanner kbd = new Scanner(System.in);
20: public static void main(String[] args) {
21: // print introduction
22: System.out.print("\n\n"
23: + "Heap Sort\n"
24: + "---------\n\n"
25: + "This program uses heap sort to sort an array.\n\n");
27: // Create list
28: System.out.print("How long should I make the list? ");
29: int numElts = kbd.nextInt();
30: kbd.nextLine();
31: int[] anArray = new int[numElts];
32: for (int i = 0; i < numElts; i++) {
33: anArray[i] = (int) (BIGGEST * Math.random());
34: }
36: // show list before sorting
37: System.out.println("\nArray values before sorting:");
38: PrintTrace.printArray(anArray);
39: pause();
41: // sort the list
42: sort(anArray);
44: // show list after sorting
45: System.out.println("\nArray values after sorting:");
46: PrintTrace.printArray(anArray);
47: pause();
48: }
50: /**
51: * Use heap sort to sort an array.
52: *
53: * @param a the array to be sorted
54: */
55: public static void sort(int[] a) {
56: // maxHeapify
57: System.out.println("Changing the list into a max-heap:");
58: for (int i = a.length / 2; i > 0; --i) {
59: System.out.println("Shifting " + a[i - 1] + " down...");
60: percolateDown(a, i, a.length);
61: PrintTrace.printArray(a, i - 1, a.length);
62: pause();
63: }
65: // report heap
66: System.out.println("\nArray values as a max-heap:");
67: PrintTrace.printArray(a);
68: pause();
70: // removeAll
71: System.out.println("Removing front items to back:");
72: int numInHeap = a.length;
73: while (numInHeap > 1) {
74: --numInHeap;
75: System.out.println("Moving " + a[0] + " to the back...");
76: int temp = a[0];
77: a[0] = a[numInHeap];
78: a[numInHeap] = temp;
79: percolateDown(a, 1, numInHeap);
80: PrintTrace.printArray(a, 0, numInHeap);
81: pause();
82: }
83: }
85: /**
86: * Help build a REVERSE heap (largest items come out first). Move the item
87: * from a[n] toward the back until it's larger than its children.
88: *
89: * @param a the array we're building the reverse heap in
90: * @param n the position we're percolating from (1-based!!!)
91: * @param len the length of the heap (or of the array we're building into a
92: * heap)
93: */
94: private static void percolateDown(int[] a, int n, int len) {
95: int temp = a[n - 1];
96: while (2 * n <= len) {
97: int l = largerChild(a, n, len);
98: if (a[l - 1] > temp) {
99: a[n - 1] = a[l - 1];
100: n = l;
101: } else {
102: break;
103: }
104: }
105: a[n - 1] = temp;
106: }
108: /**
109: * Find the larger child of position n in array a. NOTE: 1-based indexing,
110: * so the array indexes are one less than the heap positions.
111: *
112: * @param a the array the heap is in
113: * @param n the heap position (1-based) of the parent
114: * @param len the length of the heap (or of the array we're building into a
115: * heap)
116: * @return the heap position (1-based) of the larger child
117: */
118: private static int largerChild(int[] a, int n, int len) {
119: if (2 * n == len) {
120: return 2 * n;
121: }
122: return (a[2 * n - 1] > a[2 * n]) ? 2 * n : 2 * n + 1;
123: }
125: /**
126: * Wait for the user to press the enter key.
127: */
128: public static void pause() {
129: System.out.print("\n...Press ENTER...");
130: kbd.nextLine();
131: System.out.println();
132: }
134: }