public class HeapSort { private static void swap (int [] data, int i, int j) { final int temp = data[i]; data[i]=data[j]; data[j]=temp; } public static void heap_sort (int [] data, int n) { makeHeap (data, n); printArray (data, n); for (int i=n-1; i>0; i--) { swap (data, 0, i); // data[0] is max System.out.print (i+": "); printArray (data, n); reheapDown (data, i-1); } } private static void makeHeap (int [] data, int n) { for (int i=1; i<n; i++) { reheapUp (data, i); } } private static int leftSubtree (int i) { return 2*i+1; } private static int rightSubtree (int i) { return 2*i+2; } private static int parent (int i) { return (i-1)/2; } // int division /* private boolean hasLeftSubtree (int i) { return 2*i+1 < size; } private boolean hasRightSubtree (int i) { return 2*i+2 < size; } */ // Return the index of the root node's child with the larger key. // Precondition: root must be the index of an interior node private static int largerChild (int [] data, int root, int size) { final int leftChild = leftSubtree (root); final int rightChild = rightSubtree (root); if (rightChild < size && data[rightChild]>data[leftChild]) { return rightChild; } else { // Either no right subtree or left child is bigger return leftChild; } } // Assuming that the root of the heap is the only element out of // place, restore the heap property: data[Parent] >= data[Child] // O(log n) private static void reheapDown (final int [] data, int size) { int root = 0; while (2*root+1<size) { // Root is an interior node final int maxChild = largerChild (data, root, size); final int r = data[root]; final int max = data[maxChild]; if (r>=max) break; // swap data[root] = max; data[maxChild] = r; root = maxChild; } } // Assuming that the last leaf of the heap is the only element out of // place, restore the heap property: data[Parent] >= data[Child] // O(log n) private static void reheapUp (final int[] data, int bottom) { while (bottom > 0) { final int parent = parent (bottom); final int b = data[bottom]; final int p = data[parent]; if (p>=b) break; // swap data[bottom] = p; data[parent] = b; bottom = parent; } } private static void printArray (int [] data, int n) { printArray (data, 0, n); } private static void printArray (int [] data, int first, int n) { System.out.print ("["); for (int i=first; i<first+n; i++) { System.out.print (data[i]); if (i<first+n-1) System.out.print (", "); } System.out.println ("]"); } public static void main (String [] args) { int [] data = new int [1000]; int n = 0; for (int i=0; i<args.length; i++) { data[n++] = Integer.parseInt(args[i]); } printArray (data, n); heap_sort (data, n); printArray (data, n); } }