function [ indx_extract, n, indx ] = i4vec_indexed_heap_d_extract ( n, a, indx )

%*****************************************************************************80
%
%% i4vec_indexed_heap_d_extract(): extract from heap descending indexed I4VEC.
%
%  Discussion:
%
%    An I4VEC is a vector of I4's.
%
%    An indexed I4VEC is an I4VEC of data values, and an I4VEC of N indices,
%    each referencing an entry of the data vector.
%
%    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.
%
%    Note that the argument N must be a variable, which will be decremented
%    before return, and that INDX will hold one less value on output than it
%    held on input.
%
%    This is one of three functions needed to model a priority queue.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    17 August 2010
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Thomas Cormen, Charles Leiserson, Ronald Rivest,
%    Introduction to Algorithms,
%    MIT Press, 2001,
%    ISBN: 0262032937,
%    LC: QA76.C662.
%
%  Input:
%
%    integer N, the number of items in the index vector.
%
%    integer A(*), the data vector.
%
%    integer INDX(N), the index vector.
%
%  Output:
%
%    integer INDX_EXTRACT, the index in A of the item of
%    maximum value, which has now been removed from the heap.
%
%    integer N, the number of items in the
%    revised index vector.
%
%    integer INDX(N), the revised index vector.
%
  if ( n < 1 )
    fprintf ( 1, '\n' );
    fprintf ( 1, 'I4VEC_INDEXED_HEAP_D_EXTRACT - Fatal error!\n' );
    fprintf ( 1, '  The heap is empty.\n' );
    error ( 'I4VEC_INDEXED_HEAP_D_EXTRACT - Fatal error!' )
  end
%
%  Get the index of the maximum value.
%
  indx_extract = indx(1);

  if ( n == 1 )
    n = 0;
    indx = [];
    return
  end
%
%  Shift the last index down.
%
  indx(1) = indx(n);
%
%  Restore the heap structure.
%
  n = n - 1;
  indx = i4vec_indexed_heap_d ( n, a, indx );

  return
end
