package Sorter;

/**
 * Sorts an array from lo to hi by building successive heap structures.
 * <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>
 * Heapsort is part of the hard-split/easy-join family since all the work is done in
 * the split phase.

 * @dependency Sorter.Heapifier uses
 */
public class HeapSorter extends ASorter
{

   /**
	 * Constructor for this class.   Also heapifies A from  lo to hi.
	 * @param A the array to be sorted.
	 * @param lo the lo index of the sub-array
	 * @param hi the high index of the sub-array
	 */
	public HeapSorter(AOrder iCompareOp, Object[] A, int lo, int hi)
   {
      super(iCompareOp);
      Heapifier.Singleton().heapify(iCompareOp, A, lo, hi);
   }

	/**
	 * Swaps A[lo] with A[hi] and sift A[lo] down to hi - 1.
	 * Assumes A satisfies the heap property.
	 * Splits A[hi] off.
	 * @param A the array A[lo:hi] to be sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 * @return hi always
	 */
	protected int split(Object[] A, int lo, int hi)
	{
      Object temp = A[hi];
      A[hi] = A[lo];
      A[lo] = temp;
      Heapifier.Singleton().siftDown (aOrder, A, lo, lo, hi - 1);
		return hi;
	}

	/**
    * Does nothing, assuming s == hi. The sub-arrays are already in proper order.
	 */
	protected void join(Object[] A, int lo, int s, int hi)
	{
	}

}