% $Id: heapsort.slang,v 1.0 2003/01/03 14:39:00 dada Exp $
% http://dada.perl.it/shootout/
%
% contributed by John E. Davis

variable IM = 139968;
variable IA =   3877;
variable IC =  29573;

variable LAST = 42;
define gen_random(max)
{
   LAST = (LAST * IA + IC) mod IM;
   return (max * LAST) / IM;
}

define heapsort(n, ra)
{
   variable rra = 0, i = 0, j = 0;
   variable l = (n shr 1) + 1;
   variable ir = n;

   forever
     {
        if (l > 1)
      {
         l--;
         rra = ra[l];
      }
        else
      {
         rra = ra[ir];
         ra[ir] = ra[1];
         ir--;
         if (ir == 1)
           {
          ra[1] = rra;
          return;
           }
      }
        i = l;
        j = mul2(l);
        while (j <= ir)
      {
         variable raj = ra[j];
         if (j < ir)
           {
          variable raj1 = ra[j+1];
          if (raj < raj1)
            {
               j++;
               raj=raj1;
            }
           }
#iffalse
         if (rra < raj)
           {
          ra[i] = raj;
          i = j;
          j = mul2 (j);
          continue;
           }
         j = ir + 1;
#else
         if (rra >= raj)
           {
          j = ir + 1;
          break;
           }

         ra[i] = raj;
         i = j;
         j = mul2 (j);
#endif
      }

        ra[i] = rra;
     }
}


define main()
{
   variable N = integer (__argv[1]);
   if (N < 1)
     N = 1;
   variable ary = array_map (Double_Type, &gen_random, [0:N]*0+1.0);
   heapsort(N, ary);

   vmessage ("%.10f", ary[N]);
}


main();