/**
   The method sort of this class inplements in-place heap-sort
   of a sequence of integers.  The sequence is represented by
   an array.

   @author Franck van Breugel
   @version 1.1    June 3, 2002
*/
public class InPlaceHeapSorter
{
    private int[] sequence; // sequence of integers

    /**
       Constructs an object to sort the specified sequence
       of integers.
      
       @param sequence sequence to be sorted.
    */
    public InPlaceHeapSorter(int[] sequence)
    {
        this.sequence = sequence;
    }

    /**
       Sorts the sequence using in-place heap-sort.
    */
    public void sort()
    {
        for (int i = 1; i < sequence.length; i++)
	{
	    bubbleUp(i);
	}

	for (int i = 0; i < sequence.length - 1; i++)
	{
	    swap(0, sequence.length - i - 1);
	    bubbleDown(0, sequence.length - i - 1);
	}
    }

    /**
       Element with specified index is bubbled up.
      
       @param index index of element to be bubbled up.
    */
    private void bubbleUp(int index) 
    {
        if (index != 0) 
	{
	    int parent = (index - 1) / 2;
	    if (sequence[index] > sequence[parent])
	    {
		swap(index, parent);
		bubbleUp(parent);
	    }
        }
    }

    /**
       Element with specified index is bubbled down.
      
       @param index index of element to be bubbled down.
       @param size size of heap.
    */
    private void bubbleDown(int index, int size) 
    {
        if (2 * index + 1 < size) 
	{
	    int child;
	    if (2 * index + 1 == size - 1) 
	    {
		child = 2 * index + 1;
	    } 
	    else if (sequence[2 * index + 1] > sequence[2 * index + 2])
	    {
	        child = 2 * index + 1;
	    } 
            else 
	    {
		child = 2 * index + 2;
	    }
	    if (sequence[child] > sequence[index])
	    {
		swap(index, child);
		bubbleDown(child, size);
	    }
	}
    }

    /**
       Swaps the elements in the sequence with the specified indices.

       @param first index of element to be swapped.
       @param second index of element to be swapped.
    */
    private void swap(int first, int second) 
    {
        int temp = sequence[first];
        sequence[first] = sequence[second];
        sequence[second] = temp;
    }
}