public class HeapSort
{
	private void swap(int[] F, int i, int j)
	{
		int tmp = F[i];
		F[i]    = F[j];
		F[j]    = tmp;
	}
	
	private void perc(int[] F, int i, int last)
	{
		int left  = 2 * i + 1;
		int right = left  + 1;
		
		if (left <= last && right > last)
		{
			if (F[left] < F[i])
			{
				swap(F, left, i);
			}
		}
		
		if (left <= last && right <= last)
		{
			int smaller = (F[left] < F[right]) ? left : right;
			
			if (F[smaller] < F[i])
			{
				swap(F, smaller, i);
				perc(F, smaller, last);
			}
		}
	}
	
	private void build(int[] F)
	{
		for (int i = F.length/2; i >= 0; i--)
		{
			perc(F, i, F.length-1);
		}
	}
	
	private int[] reverse(int[] F)
	{		
		int[] reversedF = new int[F.length];
		
		int i = F.length-1;
		int j = 0;
		
		while (i >= 0)
		{
			reversedF[j++] = F[i--];
		}
		
		return reversedF;
	}
	
	public int[] sort(int[] F, boolean reverse)
	{
		build(F);
		
		for(int l = F.length-1; l > 0; l--)
		{
			swap(F, 0, l);
			perc(F, 0, l-1);
		}
		
		return (reverse) ? this.reverse(F) : F;
	}
	
	public int[] sort(int[] F)
	{
		return this.sort(F, false);
	}
	
	public static void main(String[] args)
	{
		int[] F     = ArrayHelper.initArray();
		HeapSort HS = new HeapSort();
		
		System.out.println(ArrayHelper.toString(F));
		System.out.println(ArrayHelper.toString(HS.sort(F, true)));
	}
}