HeapSort.java

class HeapSort {
    private static int[] a;
    private static int n;

    public static void sort(int[] arr) {
        a = arr;
        n = arr.length;
        heapsort();
    }

    private static void heapsort() {
        buildheap();
        System.out.println("After buildheap");
        report();
        while(n>1) {
            n--;
            exchange(0,n);
            downheap(0);
        }
    }

    private static void buildheap() {
        for(int v=n/2 -1; v >= 0; v--) {
            downheap(v);
        }
    }

    private static void downheap(int v) {
        int w = 2 * v +1;
        while(w < n) {
            if (w+1 < n) {
                if (a[w+1] > a[w]) {
                    w++;
                }
            }

            if (a[v] >= a[w]) {
                return;
            }

            exchange(v,w);
            v = w;
            w = 2 * v + 1;
        }
    }
    
    private static void exchange(int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;

    }

    private static void report() {
        System.out.print("Report: ---  ");
        for (int val : a) {
            System.out.print(val+",\t");
        }

        System.out.print("  ---");
    }



    public static void main(String[] args) {
        int[] intArr =  new int[] {1,60,10,2,7,90,100,35};
        System.out.println("Before ----------");
        for(int val: intArr) {
            System.out.println(val);
        }
        HeapSort.sort(intArr);
        System.out.println("After ----------");
        for(int val : intArr) {
            System.out.println(val);
        }
    }
}