/*----------------------------------------------------------------------*/ /* BOTTOM-UP HEAPSORT */ /* Written by J. Teuhola ; 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>1; while (j>=start) { if (v[j]>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 */