# Class Sorter.HeapSorter

public class HeapSorter
extends Sorter.ASorter

Sorts an array from lo to hi by building successive heap structures.

    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.

Heapsort is part of the hard-split/easy-join family since all the work is done in the split phase.

##

HeapSorter (AOrder, Object[], int, int)
  Constructor for this class

##

join (Object[], int, int, int)
  Does nothing, assuming s == hi
split (Object[], int, int)
  Swaps A[lo] with A[hi] and sift A[lo] down to hi - 1

##

HeapSorter

    public  HeapSorter(AOrder iCompareOp, Object[] A, int lo, int hi)

  Constructor for this class. Also heapifies A from lo to hi.

  Parameters:
    A - the array to be sorted.
    lo - the lo index of the sub-array
    hi - the high index of the sub-array

##

split

    protected int split(Object[] A, int lo, int 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.

  Parameters:
    A - the array A[lo:hi] to be sorted.
    lo - the low index of A.
    hi - the high index of A.
  Returns:
    hi always

join

    protected void join(Object[] A, int lo, int s, int hi)

  Does nothing, assuming s == hi. The sub-arrays are already in proper order.