/*
 *	$Id$
 *	$Log$
 */
public class HeapSortAlgorithm extends SortAlgorithm 
	{
	void HeapSort(int a[], int lo, int hi) throws Exception
		{
		int i;

		// convert the array into a heap.
		i = 1;
		while( lo + i <= hi )
			{
			siftup (a, lo, lo+i);
//			if ( heap (a, lo, lo+i) == false )	// test assertion...
//				break;
				++i;
			}

		// treat the heap as a priority queue, removing largest
		// element and rebuilding the heap.
		i = hi - lo;
		while ( i > 0 )
			{
			pause (lo, lo+i);	// mark our current location
			swap (a, lo, lo+i);	// largest element is always at 'lo'.
			--i;
			siftdown (a, lo, lo+i);
//			if ( heap (a, lo, lo+i) == false )	// test assertion...
//				break;
			}
		} 

	private void swap(int a[], int i, int j)
		{
		int T;
		T = a[i]; 
		a[i] = a[j];
		a[j] = T;
		}

	/*
	 * Verify that the heap really _is_ a heap.  Useful
	 * for debugging...
	 */
	private boolean heap (int a[], int lo, int hi)
		{
		int q = 1;
		int p;

		while ( lo+q <= hi )
			{
			p = ((q+1) / 2) - 1;
			if ( a[lo+q] > a[lo+p] )
				return false;
			++q;
			}
		return true;
		}

	/*
	 * Sift a single element into the heap.
	 * precondition:	heap (a,lo,hi-1)
	 * postcondition:  heap (a,lo,hi)
	 */
	private void siftup (int a[], int lo, int hi) throws Exception
		{
		int p = hi - lo;
		int q;

		while ( p > 0 )
			{
			q = ((p+1) / 2) - 1;
			pause (lo+p, hi);
			if (a[lo+p] <= a[lo+q])
				break;
			swap (a, lo+q, lo+p);
			p = q;
			}
		}

	/*
	 * Resettle the heap after the largest element has been removed.
	 * precondition:	heap (a,lo+1,hi) and hi > lo
	 * postcondition:  heap (a,lo,hi)
	 */
	private void siftdown (int a[], int lo, int hi) throws Exception
		{
		int p = 0;
		int q;

		while ( true )
			{
			q = (2 * (p+1)) - 1;			// q is left child of p
			if ( lo+q > hi )
				break;

			if ( lo+q+1 <= hi )
				{
				pause (lo+q, hi);
				if ( a[lo+q+1] > a[lo+q] )	// q+1 is right child of p
					++q;
				}

			pause (lo+p, hi);
			if ( a[lo+p] >= a[lo+q] )		// q is larger child of p
				break;

			swap (a, lo+p, lo+q);
			p = q;
			}
		}

	public void sort(int a[]) throws Exception
		{
		HeapSort(a, 0, a.length - 1);
		pause (-1, -1);
		}
	}