******** fig7.8 **********

	void
	heapsort( input_type a[], unsigned int n )
	{
		int i;

/*1*/		for( i=n/2; i>0; i-- )
/*2*/			perc_down( a, i, n );
/*3*/		for( i=n; i>=2; i-- )
		{
/*4*/			swap( &a[1], &a[i] );		/* delete_max */
/*5*/			perc_down( a, 1, i-1 );
		}
	}

	void
	perc_down( input_type a[], unsigned int i, unsigned int n )
	{
		unsigned int child;
		input_type tmp;

/*1*/		for( tmp = a[i]; i*2 <= n; i = child )
		{
/*2*/			child = i*2;
/*3*/			if( ( child != n ) && ( a[child+1] > a[child] ) )
/*4*/				child++;
/*5*/			if( tmp < a[child] )
/*6*/				a[i] = a[child];
			else
/*7*/				break;
		}
/*8*/		a[i] = tmp;
	}