tree delete( pq )
	tree pq;

	{tree temp;
	if ( pq == NULL ) Error /*** deletion on an empty queue ***/;
	else if ( pq->right == NULL )
		return( pq->left );
	else	{
		/*** promote left descendant up ***/
		pq->k = pq->left->k;
		pq->left = delete( pq->left );
		/*** rearrange according to constraints ***/
		if ( pq->left == NULL ) {
			pq->left = pq->right;	pq->right = NULL;  };
		if ( pq->right != NULL )
			if ( pq->left->k < pq->right->k ) {
				/*** descendants in wrong order ***/
				temp = pq->right;
				pq->right = pq->left;
				pq->left = temp;
				}
		return( pq );
		}
	};