package algorithm.sort;

public class HeapSort {

    public static void main(String[] args) {

       int[] a = new int[] {5, 3, 7, 2, 1, 4, 9, 8, 6, 1};

       sort(a);

       print(a);

    }

    public static void sort(int[] a) {

       if (a == null || a.length == 0)

           return;

       buildMaxHeap(a);

       for (int i = a.length - 1; i > 0; i--) {

           exchange(a, i, 0);

           maxHeapify(a, 0, i);

       }

    }

    private static void buildMaxHeap(int[] a) {

       for (int i = a.length / 2 - 1; i >= 0; i--) {

           maxHeapify(a, i, a.length);

       }

    }

    private static void maxHeapify(int[] a, int index, int length) {

       int largest = index;

       int left = left(index);

       if (left < length  && a[largest] < a[left])

           largest = left;

       int right = right(index);

       if (right < length && a[largest] < a[right])

           largest = right;

       if (largest == index)

           return;

       exchange(a, index, largest);

       maxHeapify(a, largest, length);

    }

    private static int left(int index) {

       return index * 2 + 1;

    }

    private static int right(int index) {

       return index * 2 + 2;

    }

    public static void exchange(int[] a, int i1, int i2) {

       int tmp = a[i1];

       a[i1] = a[i2];

       a[i2] = tmp;

    }

    public static void print(int[] a) {

       if (a == null || a.length == 0)

           return;

       for (int i = 1; i <= a.length; i++) {

           System.out.print(a[i - 1] + "\t");

           if (i % 5 == 0)

              System.out.println();

       }

    }

}