/*----------------------------------------------------------------------*/
/*                         BOTTOM-UP HEAPSORT                           */
/* Written by J. Teuhola <teuhola@cs.utu.fi>; the original idea is      */
/* probably due to R.W. Floyd. Thereafter it has been used by many      */
/* authors, among others S. Carlsson and I. Wegener. Building the heap  */
/* bottom-up is also due to R. W. Floyd: Treesort 3 (Algorithm 245),    */
/* Communications of the ACM 7, p. 701, 1964.                           */
/*----------------------------------------------------------------------*/

#define element float

/*-----------------------------------------------------------------------*/
/* The sift-up procedure sinks a hole from v[i] to leaf and then sifts   */
/* the original v[i] element from the leaf level up. This is the main    */
/* idea of bottom-up heapsort.                                           */
/*-----------------------------------------------------------------------*/
static void siftup(v, i, n)
  element v[];
  int i, n;
{ int j, start;
  element x;

  start = i;
  x = v[i];
  j = i<<1;
  while (j<=n)
    { if (j<n)
	if (v[j]<v[j+1]) j++;
      v[i] = v[j];
      i = j; j = i<<1;
    }
  j = i>>1;
  while (j>=start)
    { if (v[j]<x)
	{ v[i] = v[j];
	  i = j; j = i>>1;
	}
      else break;
    }
  v[i] = x;
}                                /* End of siftup */

/*----------------------------------------------------------------------*/
/* The heapsort procedure; the original array is r[0..n-1], but here    */
/* it is shifted to vector v[1..n], for convenience.                     */
/*----------------------------------------------------------------------*/
void bottom_up_heapsort(r, n)
  element r[];
  int n;
{
  int k; 
  element x;
  element *v;

  v = r-1;                   /* The address shift */

/* Build the heap bottom-up, using siftup. */
  for (k=n>>1; k>1; k--) siftup(v, k, n);

/* The main loop of sorting follows. The root is swapped with the last  */
/* leaf after each sift-up. */
  for (k=n; k>1; k--)
    {
      siftup(v, 1, k);
      x = v[k]; v[k] = v[1]; v[1] = x;
    }
}                                /* End of bottom_up_heapsort */