procedure delete ( var pq : tree );
	var	temp : tree;
	begin
	if pq = nil then Error {*** deletion on an empty queue ***}
	else if pq^.right = nil then
		pq := pq^.left
	else	begin
		{*** promote left descendant up ***}
		pq^.k := pq^.left^.k;
		delete( pq^.left );
		{*** rearrange according to constraints ***}
		if pq^.left = nil then begin
			pq^.left := pq^.right;	pq^.right := nil  end;
		if pq^.right <> nil then
			if pq^.left^.k < pq^.right^.k then begin
				{*** descendants in wrong order ***}
				temp := pq^.right;
				pq^.right := pq^.left;
				pq^.left := temp
				end
		end
	end;