public class HeapSort
{
	public static void main( String args[] )
	{
		int arr[] = { 6, 10, 5, 12, 3, 9, 20, 2, 15, 8, 18 };
		heapSort( arr );
		printArray( arr );
	}

	public static void printArray( int s[] )
	{
		for( int i = 0; i < s.length; i++ )
		{
			System.out.print( s[i] + " " );
		}
		System.out.println();
	}

	public static int parent( int child )
	{
		return ( child - 1 ) / 2;
	}

	public static int left( int parent )
	{
		return parent*2 + 1;
	}

	public static int right( int parent )
	{
		return parent*2 + 2;
	}

	public static boolean isNotLeaf( int node, int heapEnd )
	{
		// return left( node ) < heapEnd; ----- wrong!
		return left( node ) <= heapEnd;
	}

	public static void heapSort( int s[] )
	{
		int n = s.length;

		// build heap
		for( int i = 1; i <= n-1; i++ )
		{
			// insert s[i] into s[0]-s[i-1] heap
			int node = i;
			while( node > 0 && (s[node] > s[parent(node)]) )
			{
				// swap s[node] and s[parent(node)]
				int p = parent(node);
				int temp = s[node];
				s[node] = s[p];
				s[p] = temp;

				node = p; // move to parent
			}
		}

		// repeatedly select maximum, place in proper position, then rearrange
		for( int i = n-1; i >= 1; i-- )
		{
			// swap s[0] and s[i]
			int temp = s[0];
			s[0] = s[i];
			s[i] = temp;

			// rearrange
			int heapEnd = i-1;
			int node = 0;
			while ( isNotLeaf( node, heapEnd ) )
			{
				// select child with maximum value
				int pos = left(node);
				if ( pos != heapEnd )
				{
					int rc = right(node);
					if ( s[rc] > s[pos] )
						pos = rc;
				}

				// if heap property violated, swap
				if ( s[pos] > s[node] )
				{
					// swap s[pos] and s[node]
					temp = s[pos];
					s[pos] = s[node];
					s[node] = temp;
					node = pos;
				}
				else
				{
					// otherwise, fall out of the while loop
					break;
				}
			}
		}

	}

}