# heap sort BEGIN { for (i=0; i<=20; i++) tester(i) tester(1000) } function tester(i) { genid(x,i); sort(x,i); check(x,i); clear(x) gensort(x,i); sort(x,i); check(x,i); clear(x) genrev(x,i); sort(x,i); check(x,i); clear(x) genrand(x,i); sort(x,i); check(x,i); clear(x) } function genid(x,n, i) { for (i=1; i<=n; i++) x[i] = 1 } function gensort(x,n, i) { for (i=1; i<=n; i++) x[i] = i } function genrev(x,n, i) { for (i=1; i<=n; i++) x[i] = n + 1 - i } function genrand(x,n, i) { for (i=1; i<=n; i++) x[i] = int(n * rand()) } function check(x,n, i) { for (i=1; i=1; i--) heapify(A, i, n) for (i=n; i>1; i--) { swap(A, 1, i) heapify(A, 1, i-1) } } # move swap inline, move invariant part of swap out of inner loop function heapify(A,left,right, p,c,t) { t = A[left] for (p=left; (c=2*p) <= right; p=c) { if (c=1; i--) heapify(A, i, n) for (i=n; i>1; i--) { t = A[1]; A[1] = A[i]; A[i] = t heapify(A, 1, i-1) } } # sift all the way down, then back up function heapify(A,left,right, p,c,t) { t = A[left] for (p=left; (c=2*p) <= right; p=c) { if (c= left; c=p) { if (t > A[p]) A[c] = A[p]; else break } A[c] = t } function sort(A,n, i,t) { for (i=int(n/2); i>=1; i--) heapify(A, i, n) for (i=n; i>1; i--) { t = A[1]; A[1] = A[i]; A[i] = t heapify(A, 1, i-1) } } # move heapify code inline function sort(A,n, l,r,p,c,t) { if (n > 1) { l = int(n/2) + 1; r = n while(1) { if (l > 1) t = A[--l] else { t = A[r]; A[r--] = A[1] if (r == 1) { A[1] = t; return } } for (p=l; (c=2*p) <= r; p=c) { if (c < r && A[c] < A[c+1]) c++ A[p] = A[c] } for (c=p; (p=int(c/2)) >= l; c=p) { if (A[p] < t) A[c] = A[p]; else break } A[c] = t } } }