package Sorter;

/**
* Maintains the heap structure of a given array.
<pre>
An array A[lo:hi] is said to satisfy the "heap property" if for i = 0, 1, .., 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].
</pre>

*/
public class Heapifier
{
   private static final Heapifier instance  = new Heapifier ();

   private Heapifier()
   {
   }

   public static Heapifier Singleton()
   {
      return instance;
   }
   /**
   * "Sifts" A[cur] up the array A to maintain the heap property.
   * @param A A[lo:cur-1] is a heap.
   * @param lo the low index of A.
   * @param cur lo <= cur <= the high index of A.
   */
	public void siftUp(AOrder iCompareOp, Object[] A, int lo, int cur)
	{
      int parent = (cur - lo - 1) / 2 + lo;  // index of parent.
      if (0 < (cur - lo) && iCompareOp.lt(A[parent], A[cur]))
      {
        Object dat = A[cur];
         A[cur] = A[parent];
        A[parent] = dat;
        siftUp(iCompareOp, A, lo, parent);
      }
	}


	/**
    * "Sifts" the value at A[cur] down the array A to maintain the heap property.
	 * @param A  A[cur + 1:hi] satisfies the heap property.
    * @param lo the low index of A.
	 * @param cur lo <= cur <= hi.
	 * @param hi  the high index of a.
	 */
	public void siftDown(AOrder iCompareOp, Object[] A, int lo, int cur, int hi)
	{
      int child = 2 * (cur -lo) + 1 + lo; // index of left child of A[cur].
      if(hi>=child)
      {
         if ((child < hi) && iCompareOp.lt(A[child], A[child + 1]))
         {
            child++; // select the right child
         } // child is the index of the smaller of the two children.
         if (iCompareOp.lt(A[cur], A[child]))
         {
            Object dat = A[cur]; // swap the data.
            A[cur] = A[child];
            A[child] = dat;
            siftDown(iCompareOp, A, lo, child, hi);
         }  // A[cur] is less than its children.
      } // location found for temp.
	}


  public void heapify(AOrder iCompareOp, Object[] A, int lo, int hi)
  {
      if((hi-lo)>0)
      {
        for(int i = (hi-lo-1)/2;i>=0; i--)
        {
          siftDown(iCompareOp, A, lo, i, hi);
        }
      }

  }
}