8.3 Heapsort 337 01 as 6 http://www.nr. 83 d10 a12 鱼 18881892 Figure 8.3.1. Ordering implied by a "heap,"here of 12 elements.Elements connected by an upward path are sorted with respect to one another,but there is not necessarily any ordering among elements 1-600 related only "laterally." from NUMERICAL RECIPESI the corporate ladder.Each employee is brought in at the top of the tree,but then 6 immediately sifted down,with more capable workers promoted until their proper corporate level has been reached. (Nort server 9 In the Heapsort implementation,the same "sift-up"code can be used for the initial creation of the heap and for the subsequent retirement-and-promotion phase. Ameri computer One execution of the Heapsort function represents the entire life-cycle of a giant ART corporation:N/2 workers are hired;N/2 potential supervisors are hired;there is a 9 Program sifting up in the ranks,a sort of super Peter Principle:in due course,each of the original employees gets promoted to chairman of the board. void hpsort(unsigned long n,float ra]) Sorts an array ra[1..n]into ascending numerical order using the Heapsort algorithm.n is input;ra is replaced on output by its sorted rearrangement. unsigned long i,ir,j,1; float rra; 1788-1982 OF SCIENTIFIC COMPUTING(ISBN if (n 2)return; 1=(n>>1)+1; 12-521 1r=n; The index 1 will be decremented from its initial value down to 1 during the "hiring"(heap creation)phase.Once it reaches 1,the index ir will be decremented from its initial value Numerical Recipes 43108 down to 1 during the "retirement-and-promotion"(heap selection)phase. for(;;)[ 1f(1>1)[ Still in hiring phase. (outside rrasra[--1]; Software. else In retirement-and-promotion phase. North rra=rafir]; Clear a space at end of array. ra[ir]-ra[1]; Retire the top of the heap into it Amer 1f(--1r==1)[ Done with the last promotion. ra[i]=rra; The least competent worker of all! break; 11; Whether in the hiring phase or promotion phase,we j=1+1; here set up to sift down element rra to its proper while (j <ir){ evel if (i<ir &ra[i]ra[j+1])++; Compare to the better underling. if (rra ra[j]){ Demote rra. ra[i]=ra[j];8.3 Heapsort 337 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). a1 a2 a3 a7 a6 a5 a4 a8 a9 a10 a11 a12 Figure 8.3.1. Ordering implied by a “heap,” here of 12 elements. Elements connected by an upward path are sorted with respect to one another, but there is not necessarily any ordering among elements related only “laterally.” the corporate ladder. Each employee is brought in at the top of the tree, but then immediately sifted down, with more capable workers promoted until their proper corporate level has been reached. In the Heapsort implementation, the same “sift-up” code can be used for the initial creation of the heap and for the subsequent retirement-and-promotion phase. One execution of the Heapsort function represents the entire life-cycle of a giant corporation: N/2 workers are hired; N/2 potential supervisors are hired; there is a sifting up in the ranks, a sort of super Peter Principle: in due course, each of the original employees gets promoted to chairman of the board. void hpsort(unsigned long n, float ra[]) Sorts an array ra[1..n] into ascending numerical order using the Heapsort algorithm. n is input; ra is replaced on output by its sorted rearrangement. { unsigned long i,ir,j,l; float rra; if (n < 2) return; l=(n >> 1)+1; ir=n; The index l will be decremented from its initial value down to 1 during the “hiring” (heap creation) phase. Once it reaches 1, the index ir will be decremented from its initial value down to 1 during the “retirement-and-promotion” (heap selection) phase. for (;;) { if (l > 1) { Still in hiring phase. rra=ra[--l]; } else { In retirement-and-promotion phase. rra=ra[ir]; Clear a space at end of array. ra[ir]=ra[1]; Retire the top of the heap into it. if (--ir == 1) { Done with the last promotion. ra[1]=rra; The least competent worker of all! break; } } i=l; Whether in the hiring phase or promotion phase, we here set up to sift down element rra to its proper level. j=l+l; while (j <= ir) { if (j < ir && ra[j] < ra[j+1]) j++; Compare to the better underling. if (rra < ra[j]) { Demote rra. ra[i]=ra[j];