TestHeap.java

/*
    TestHeap.java
    David G. Klick
    CIS 260
    2010-01-21
   
    Demonstration of programming a heap sort.
*/

public class TestHeap {
    static final int DEFAULT_SIZE = 100;
    
    public static void main(String[] args) {
        int size = DEFAULT_SIZE;
        switch (args.length) {
            case 0: break;
            case 1:
                try {
                    size = Integer.parseInt(args[0]);
                    if (size<3 || size>200) {
                        System.out.println("Size is outside of allowed range (3-200). Using default size.");
                        size = DEFAULT_SIZE;
                    }
                } catch (NumberFormatException e) {
                    System.err.println("Invalid argument. Using default array size.");
                }
                break;
            default:
                System.err.println("Invalid number of arguments. Using default array size.");
        }
        
        int[] nums = new int[size];
        java.util.Random rand = new java.util.Random();
        for (int i=0; i<nums.length; i++) nums[i] = rand.nextInt();
        System.out.println("Before sorting:");
        displayArray(nums);
        heapsort(nums);
        System.out.println("After sorting:");
        displayArray(nums);
    }
    private static void displayArray(int[] a) {
        for (int i=0; i<a.length; i++) {
            System.out.printf("%12d", a[i]);
            if (i % 6 == 5) System.out.println();
        }
        System.out.println();
    }
    
    private static void heapsort(int[] arr) {
        heapify(arr);
        int last = arr.length - 1;
        while (last > 0) {
            swap(arr, last, 0);
            siftdown(arr, 0, --last);
        }
    }

private static void heapify(int[] arr) {
        int len = arr.length;
        int current = (len-2) / 2;
        while (current >= 0) { 
            siftdown(arr, current--, len-1);
        }
    }

private static void siftdown(int[] arr, int ndx, int last) {
        int base = ndx;
        while (base*2+1 <= last) {
            int child = base * 2 + 1;  // left child
            if (child+1 <= last && arr[child] < arr[child+1]) child++;
            if (arr[base] < arr[child]) {
                swap(arr, base, child);
                base = child;
            } else break;
        }
    }
    
    private static void swap(int[] arr, int n1, int n2) {
        int tmp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = tmp;
    }
}