/**
* Maintains the max-heap structure of a given array.
An array A[lo:hi] is said to satisfy the "max-heap property" if
for i = 0,.., hi - lo:
A[lo + i] >= A[lo + 2 * i + 1]  and
A[lo + i] >= A[lo + 2 * i + 2],
whenever these indices are in the range [lo..hi].

* 
 Copyright 2000 - Dung X. Nguyen - All rights reserved. 
* 
 Copyright 2008 - Mathias Ricken - All rights reserved. 
*/
public class Heapifier {
    public static final Heapifier Singleton = new Heapifier ();
    private Heapifier() {
    }

    /**
    * "Sifts" A[cur] up the array A to maintain the max-heap property.
    * @param A A[lo:cur-1] is a max-heap.
    * @param lo the low index of A.
    * @param cur lo <= cur <= the high index of A.
    */
    public void siftUp(int[] A, int lo, int cur) {
        int dat = A[cur];
        int parent = (cur - lo - 1) / 2 + lo;  // index of parent.
        while (0 < (cur - lo) && dat > A[parent]) {
            A[cur] = A[parent];
            cur = parent;
            parent = (cur - lo - 1) / 2 + lo;
        }
        A[cur] = dat;
    }


    /**
    * "Sifts" the value at A[cur] down the array A to maintain the max-heap property.
    * @param A  A[cur + 1:hi] satisfies the max-heap property.
    * @param lo the low index of A.
    * @param cur lo <= cur <= hi.
    * @param hi  the high index of a.
    */
    public void siftDown(int[] A, int lo, int cur, int hi) {
        int dat = A[cur]; // hold on to data.
        int child = 2 * cur + 1 - lo; // index of left child of A[cur].
        boolean done = hi < child;
        while (!done) {
            if (child < hi && A[child + 1] > A[child]) {
                child++;
            } // child is the index of the greater of the two children.
            if (A[child] < dat) {
                A[cur] = A[child];
                cur = child;
                child = 2 * cur + 1 - lo;
                done = hi < child;
            }  // parent of A[cur] > dat.
            else {// dat >= A[child], the greater of the children of A[cur].
                done = true;  // max-heap condition is satisfied.
            } // A[cur] is greater than its children.
        } // location found for dat.
        A[cur] = dat;
    }

    /**
     * Simple test program.
     */
    public static void main(String[] args)  {
        int[] A =  {999, 50, 80, 20, 60, 90, 40, 30, 70, 10, -999};
        int arrayLen = A.length;
        System.out.println ("A =");
        for (int i = 0; i < arrayLen; i++) {
            System.out.print (A[i] + "  ");
        }
        System.out.println ();

        int lo = 1;
        int hi = arrayLen - 2;
        System.out.println ("Heapifying A[" + lo + "..." + hi + "]");
        for (int cur = (hi - lo + 1) / 2; cur >= lo; cur--) {
            Heapifier.Singleton.siftDown (A, lo, cur, hi);
        }
        System.out.println ("Heapified A =");
        for (int i = 0; i < A.length; i++)  {
            System.out.print (A[i] + "  ");
        }

        System.out.println ("\nSifting -999 up A[" + lo + "..." + hi + "]");
        Heapifier.Singleton.siftUp (A, lo, hi + 1);
        System.out.println ("Heapified A =");
        for (int i = 0; i < A.length; i++) {
            System.out.print (A[i] + "  ");
        }

        System.out.println ("\nDone");
    }
}