/* rotina para escolher entre nmin e nmax melhores dentre nin dados.
   os dados estao no vetor value em ordem crescente de valores.
   voce quer os nmax menores valores
   retorna indice do ultimo val nao incluido*/
int n_melhor(int nmin, int nmax, float value[])
{
  int nout;

  nout = nmin;
  if (nmin > 1)
  { float avggap = (value[nmin-1]-value[0])/((float)nmin);
    float lastgap = value[nmin-1]-value[nmin-2];
    float tiegap = (lastgap < avggap ? lastgap : avggap);
    while(
      (nout < nmax) &&
      ((value[nout]-value[nout-1]) <= tiegap)
    ) nout++;
  }
  return(nout);
}



/* funcao para ordenar em ordem crescente um vetor de valores e
   um respectivo vetor de inteiros */
void sort(int n, float value[], int elem[])
  { int p, q, r, mx;
    float cc, vmax;
    int ccelem;
        
    /* 1. Build heap with largest element at value[0] */
    for (p = 0; p<n; p++)
      { cc = value[p]; 
	ccelem = elem[p];
	r = p;
	while(r > 0)
	  { q = (r-1) / 2;
	    if (value[q] < cc) 
	      { value[r] = value[q]; 
		elem[r] = elem[q];
	      }
	    else break;
	    r = q;
	  }
	value[r] = cc; 
	elem[r] = ccelem;
      }

    /* 2. Remove elements from heap and insert at end */
    for (p = n-1; p > 0; p--)
      { 
	/* save value[p] */
	cc = value[p]; 
	ccelem = elem[p];
	/* Move largest heap element to povalue[p] */
	value[p] = value[0]; 
	elem[p] = elem[0];
	/* Insert cc in remaining heap, from root down  */
	q = 0;
	while(1)
	  {
	    value[q] = cc; 
	    elem[q] = ccelem;
	    r = 2*q+1;
	    /* Find largest among cc, value[LEFT(q)], value[RIGHT(q)]  */
	    mx = q; vmax = cc;
	    if ((r<p)&&(value[r]>vmax))
	      { mx = r; vmax = value[r]; }
	    r++;
	    if((r<p)&&(value[r]>vmax))
	      { mx = r; vmax = value[r]; }
	    /*  See who won  */
	    if (mx==q) break;
	    /*  Promote child and advance  */
	    value[q] = value[mx];  
	    elem[q] = elem[mx]; 
	    q = mx;
	  }
      }
  }