public class HeapSorter
{
    private int[] a;
    private String[] b;
    private int n;    
    public HeapSorter ()
    {
    }


    public void sort (int[] a0)
    {
	a = a0;
	n = a.length;
	heapsort ();
    }


    public void srt2 (int[] a0, String[] b0)
    {
	a = a0;
	b = b0;
	n = a.length;
	heapsrt2 ();
    }


    private void heapsort ()
    {
	buildheap ();
	while (n > 1)
	{
	    n--;
	    exchange (0, n);
	    downheap (0);
	}
    }


    private void heapsrt2 ()
    {
	buildhp2 ();
	while (n > 1)
	{
	    n--;
	    exchnge2 (0, n);
	    downhp2 (0);
	}
    }


    private void buildheap ()
    {
	for (int v = n / 2 - 1 ; v >= 0 ; v--)
	    downheap (v);
    }    
    
    
    private void buildhp2 ()
    {
	for (int v = n / 2 - 1 ; v >= 0 ; v--)
	    downhp2 (v);
    }


    private void downheap (int v)
    {
	int w = 2 * v + 1; // first descendant of v
	while (w < n)
	{
	    if (w + 1 < n) // is there a second descendant?
		if (a [w + 1] > a [w])
		    w++;
	    // w is the descendant of v with maximum label

	    if (a [v] >= a [w])
		return;                  // v has heap property
	    // otherwise
	    exchange (v, w); // exchange labels of v and w
	    v = w;      // continue
	    w = 2 * v + 1;
	}
    }


    private void downhp2 (int v)
    {
	int w = 2 * v + 1;
	while (w < n)
	{
	    if (w + 1 < n)
		if (a [w + 1] < a [w])
		    w++;


	    if (a [v] <= a [w])
		return;

	    exchnge2 (v, w);
	    v = w;
	    w = 2 * v + 1;
	}
    }


    private void exchange (int i, int j)
    {
	int t = a [i];        
	a [i] = a [j];        
	a [j] = t;        
    }


    private void exchnge2 (int i, int j)
    {
	int t = a [i];        
	a [i] = a [j];
	a [j] = t;
	String u = b [i];
	b [i] = b [j];
	b [j] = u;
    }
} // end class HeapSorter