function [ value, n, a ] = i4vec_heap_d_extract ( n, a, value )

%*****************************************************************************80
%
%% i4vec_heap_d_extract() extracts the maximum value from a descending heap.
%
%  Discussion:
%
%    An I4VEC is a vector of integer values.
%
%    In other words, the routine finds the maximum value in the
%    heap, returns that value to the user, deletes that value from
%    the heap, and restores the heap to its proper form.
%
%    This is one of three functions needed to model a priority queue.
%
%  Licensing:
%
%    This code is distributed under the MIT license. 
%
%  Modified:
%
%    05 November 2005
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Thomas Cormen, Charles Leiserson, Ronald Rivest,
%    Introduction to Algorithms,
%    MIT Press, page 150.
%
%  Input:
%
%    integer N, the number of items in the heap.
%
%    integer A(N), the heap.
%
%  Output:
%
%    integer VALUE, the item of maximum value, which has been
%    removed from the heap.
%
%    integer N, the number of items in the heap.
%
%    integer A(N), the heap.
%
  if ( n < 1 )
    fprintf ( 1, '\n' );
    fprintf ( 1, 'I4VEC_HEAP_D_EXTRACT - Fatal error!\n' );
    fprintf ( 1, '  The heap is empty.\n' );
    error ( 'I4VEC_HEAP_D_EXTRACT - Fatal error!' );
  end
%
%  Get the maximum value.
%
  value = a(1);

  if ( n == 1 )
    n = 0;
    return
  end
%
%  Shift the last value down.
%
  a(1) = a(n);
%
%  Restore the heap structure.
%
  n = n - 1;
  a = i4vec_sort_heap_d ( n, a );

  return
end
