public class BinaryHeaps1{
    private static int size = 6;

    public static void printHeap(int a[]) {
        for (int i = 1; i <=size; i++) {
            System.out.print (a[i] + "  ");
        }
        System.out.println();
    }

    public static void buildHeap(int a[]) { // O(n) worst case
        for (int i = (size/2); i >=1; i--){
            percolateDown(a, i);
        }
    }

    public static void swap (int a[], int b, int c) {
        int temp = a[b];
        a[b] = a[c];
        a[c] = temp;
    }

    public static int getLeftCell (int cell) {
        return (2 * cell);
    }

    public static int getRightCell (int cell)   {
        return (2 * cell + 1);
    }

    public static int getParent(int cell){
        return (cell/2);
    }

    public static void insert(int a[], int value ){ // O(log n) worst case, O(1) average case
        size++;
        a[size]= value;
        System.out.println ("Inserting " + value);
        percolateUp(a);
    }

    public static void percolateUp(int a[]){ // O(log n) worst case
        int cell = size;
        while (cell > 1 && a[cell] < a[cell/2]){
            swap (a, cell, cell/2);
            cell = cell/2;
        }
    }

    public static int deleteMin(int a[]){ // O(log n ) worst case,  O(log n )) average case
        int value = a[1];
        a[1] = a[size];
        a[size] = 0;
        size--;
        percolateDown(a,1);
        return value;

    }

    public static boolean isLeaf (int cell){
        return cell > size/2 ? true: false;
    }

    public static void percolateDown(int a[], int cell)  { // O(log n ) worst case
        boolean flag = true;
        while (flag){
            int left = getLeftCell (cell);
            int right = getRightCell (cell);
            if (left <=size) {
                if ( right >  size){
                    flag = false;
                    if (a[left] < a[cell]){
                        swap(a, left, cell);
                    }
                }
                else{
                    int mincell = 0;
                    if( a[left] <= a[right] )  {
                        mincell = left;
                    }
                    else{
                        mincell = right;
                    }
                    if (a[mincell] < a[cell]){
                        swap(a, mincell, cell);
                        if (!isLeaf(mincell)){
                            cell = mincell;
                        }
                    }
                    else{
                        flag = false;
                    }
                }
            }
            else{
                flag = false;
            }
        }
    }

    public static void heapSort(int a[]){
        while (size > 0){
            System.out.print (deleteMin(a) + "  " );
        }
    }

    public static void main(String args[]) {
        int a[] = {0,16,5,14,3,12,1,0,0,0};
        System.out.println ("Starting Array");
        for (int i : a){
            System.out.print(i + "  " );
        }
        System.out.println();
        buildHeap(a);
        System.out.println ("Min heap : " );
        printHeap(a);
        insert(a, -1);
        printHeap(a);
        // deleteMin(a);
        // printHeap(a);
        System.out.println ("Heap Sort");
        heapSort(a);
    }
}