第1章 概述假設f(n)和g(n)為兩個定義域為自然數的正函數。證明f(n)+g(n)=(max(f(n),g(n)))。證明：因為對任一n≥0，max(f(n),g(n))≤f(n)+g(n)≤2max(f(n),g(n))，所以有f(n)+g(n)=O(max(f(n),g(n)))和f(n)+g(n)=(max(f(n),g(n)))，也就是f(n)+g(n)=(max(f(n),g(n)))。假設f(n)=(p(n))，g(n)=(q(n))，并且都是正函數。證明以下結論。f(n)+g(n)=(p(n)+q(n))f(n)g(n)=(p(n)q(n))f(n)/g(n)=(p(n)/q(n))證明：因為f(n)=(p(n))，g(n)=(q(n))，所以存在常數a0,b0,c0,d0和n0使得當n≥n0時有ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)。從以上關系可知，當n≥n0時，ap(n)+cq(n)≤f(n)+g(n)≤bp(n)+dq(n)。讓u=min(a,c),v=max(b,d)，上式可寫為u(p(n)+q(n))≤f(n)+g(n)≤v(p(n)+q(n))所以有f(n)+g(n)=(p(n)+q(n))。由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)，我們可得，當n≥n0時，ap(n)cq(n)≤f(n)g(n)≤bp(n)dq(n)。讓u=ac,v=bd，上式可寫為u(p(n)q(n))≤f(n)g(n)≤v(p(n)q(n))。所以有f(n)g(n)=(p(n)q(n))由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n),我們可得，當n≥n0時，ap(n)/dq(n)≤f(n)/g(n)≤bp(n)/cq(n)。讓u=a/d,v=b/c，上式可寫為u(p(n)/q(n))≤f(n)/g(n)≤v(f(n)/q(n))。所以有f(n)/g(n)=(p(n)/q(n))。對以下每個函數，用theta()記號表示與其同階的只含一項的函數。例如，f(n)=(n+1)3可表示為f(n)=(n3)。(a)f(n)=n2+nlgn(b)f(n)=n(c)f(n)=(解：(a)f(n)=n2+nlgn=Q(n2)(b)f(n)=n(nlgn+2n)lg2n+n=Q((c)f(n)=(n2+lgn)(n+1)n+n用theta()記號表示對下面一段程序中語句x?x+1被執行的次數的估計。fori?1tonforj?ito3ix?x+1; endforendfor解：T(n)=i=1=i=1=2n(n+1)2+=Q(n2)。對以下每個級數和T(n)，用theta()記號表示與其同階的只含一項的函數。T(n)=k=1T(n)=k=1解：(a)因為T(n)=k=1nk3lgk+1kT(n)<ck=1nklgk<c=cn2lgn。所以有T(n)=O(n又因為T(n)=k=1nΘ(klgk)T(n)>dk=1nklgk>dk=n/2nklgk>dk=n/2nn/2lgn/2=dn所以有T(n)=(n2lgn)和T(n)=(n2lgn)。(b)T(n)=k=1nk+klgk+83k2lgk+5k+1在我們討論例1.3的線性搜索算法的平均復雜度時，我們假設數字x總可以在數組A中找到。這簡化了問題。如果我們假定，x不出現在數組A中的概率是Pr(xA[1..n])=0.2，而x等于A中任一個數的概率相同，即Pr(x=A[1])=Pr(x=A[2])=…=Pr(x=A[n])，求線性搜索算法的平均復雜度。解：平均復雜度是：0.2n+1?0.2n(1+2+…+n)=0.2n+0.8n+12=0.6第2章 分治法用分治法設計一個算法找出數組A[1..n]中的最大的數，并分析所需的比較次數。解：以下用分治法的算法是作用在數組A[p,r]上的，p≤r。在調用該算法時，只須置p=1，r=n即可。Maximum(A[p..r],Max)ifp=rthenMaxA[p] exitendifq(p+r)/2Maximum(A[p..q],Max1)Maximum(A[q+1,r],Max2)Maxmax{Max1,Max2}End 我們用T(n)表示數組中數字間的比較次數，則有以下遞推關系：T(n)=T(n/2)+T(n/2)+1T(1)=0我們用歸納法證明T(n)=n–1。歸納基礎：因為T(1)=0，所以T(n)=n–1顯然在n=1時正確。歸納步驟：由遞推關系和歸納假設我們有以下推導：T(n)=T(n/2)+T(n/2)+1=(n/2-1)+(n/2-1)+1=n/2+n/2-1=n–1。歸納成功。用分治法設計一個算法同時找出數組A[1..n]中的最大和第二大的數，n2，并分析所需的比較次數。解：以下分治法的算法是作用在數組A[p,r]上的,p≤r。在調用該算法時，只須置p=1，r=n即可。Largest-and-second-largest(A[p..r],L,S)//L和S分別為最大和第二大的數ifp=rthenL?A[p] S?- //表示沒有第二大數endifq??(p+r)/2?Largest-and-second-largest(A[p..q],L1,S1)Largest-and-second-largest(A[q+1..r],L2,S2)ifL1>L2thenL?L1 S?max{L2,S1}elseL?L2 S?max{L1,S2}endif End我們用T(n)表示數組中數的比較次數，則有以下遞推關系：T(n)=T(?n/2?)+T(én/2ù)+2 T(1)=0它的解可用主方法得到。令n=2k，則有T(n)=2T(n/2)+2=Q(n)。如果想知道更為準確的常數因子，我們可用歸納法證明T(n)=2n–2。歸納基礎：因為T(1)=0所以T(n)=2n–2顯然在n=1時正確。歸納步驟：由遞推關系和歸納假設有以下推導：T(n)=T(?n/2?)+T(én/2ù)+2=(2?n/2?-2)+(2én/2ù-2)+2=(2n-4)+2=2n–2。歸納成功。假設GOOGLE公司在過去n天中的股票價格記錄在數組A[1..n]中。我們希望從中找出兩天的價格，其價格的增幅最大。也就是說，我們希望找到A[i]和A[j]，i<j，使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1i<jn}。試設計一個復雜度為O(nlgn)或更好的分治算法。解：以下算法找出數組A[p..r]中序號i和j使得M=A[j]–A[i]的值最大，pi<jr。Divide-Conquer-Max-profit(p,r,m,i,j)//假設r3pifp=r thenm?-￥ exit //m=-￥表示只有一天的價格endifq=?(p+r)/2?Divide-Conquer-Max-profit(p,q,ml,il,jl)Divide-Conquer-Max-profit(q+1,r,mr,ir,jr)FindxsuchthatA[x]=min(A[p],…,A[q])FindysuchthatA[y]=max(A[q+1],…,A[r])mc?A[y]–A[x]ifmc3max{ml,mr} thenm?mc i?x j?y elseifml3mr thenm?ml i?il j?jl elsem?mr i?ir j?jr endifendifEnd調用Divide-Conquer-Max-profit(1,n,m,i,j)后即可找到對數組A[1..n]的解。上面算法的復雜度可由下面遞推關系求出：T(n)=T(?n/2?)+T(én/2ù)+Q(n)=Q(nlgn)。稍加修改后，我們可以得到O(n)復雜度的分治術算法。我們留給讀者思考。設A和B是兩個nn矩陣。眾所周知，計算乘積C=AB通常需要(n3)次乘法和加法。基於分治術的Strassen算法可以改進這個復雜度。下面是這個算法。為簡化起見，我們假設n=2k。Strassen’salgorithm(A,B,n);將A和B各自劃分為4個n/2n/2的矩陣如下。A=A11A12A按下面公式遞歸計算出7個n/2n/2的矩陣。P=(A11+A22)(B11+B22); Q=(A21+A22)B11;R=A11(B12–B22); S=A22(B21-B11);T=(A11+A22)B22; U=(A21-A11)(B11+B12);V=(A12–A22)(B21+B22)。按下面公式計算出4個n/2n/2的矩陣。C11=P+S–T+V

; C12=R+T

;C21=Q+S; C22=P+R–Q+U;輸出結果如下。C=AB=C11請分析Strassen算法的復雜度。你不必證明其正確性。解: 將A和B各自劃分為4個n/2′n/2的矩陣后，第2步和第3步遞歸地進行7次n/2′n/2矩陣之間的乘法和18次n/2′n/2矩陣間的加法。所以，我們可以有以下的遞推關系：T(n)=7T(n/2)+18n2它的解是T(n)=Q()=Q()。如果我們只考慮乘法次數，那么其遞推關系是T(n)=7T(n/2)，它的解仍是T(n)=Q()=Q()。證明式（2.1）滿足T(n)=T(?n/2?)+1lg(n+1)。證明：我們用歸納法證明。歸納基礎：當n=0時，式（2.1）給出T(0)=0。因為lg(0+1)=0，命題T(n)lg(n+1)正確。當n=1時，T(1)=T(0)+1=1。因為lg(1+1)=1，命題T(n)lg(n+1)也正確。歸納步驟：假設當n=0，1，2，…，k-1（k2）時我們有T(n)lg(n+1)。我們證明當n=k時也有T(n)lg(n+1)。由遞推關系，我們有T(k)=T(?k/2?)+1。因為k2，有?k/2?k-1。從歸納假設，T(?k/2?)lg(?k/2?+1)，從而有：T(k)=T(?k/2?)+1lg(?k/2?+1)+1=lg(?k/2?+1)+1=lg(?k/2?+1)+lg2=lg(2?k/2?+2)。如果k是一個奇數，我們有：T(k)lg(2?k/2?+2)=lg(2(k-1)/2?+2)=lg(k+1)。 如果k是一個偶數，我們有：T(k)lg(2?k/2?+2)。=lg(k+2)=lg(k+1)。（因為k+1是奇數，向上取整后，兩者相等。）歸納成功。用替換法獲得以下遞推關系的一個漸近上界。(a) T(n)=T(n/2)+2T(n/4)解: 我們歸納證明，存在一個正數c使得T(n)≤cn。歸納基礎：顯然我們可以找到正數c，使得在n=1，2，3，4時，T(n)≤cn。歸納步驟：假設存在正數c，當n=1，2，3，4，5，…，k-1（k5）時我們有T(n)￡cn。我們證明當n=k時也有T(n)￡cn。因為當n5時有n/2<n，n/4<n，由歸納假設有T(n/2)￡cn/2和T(n/4)cn/4。把這兩個關系代入到原遞歸關系中，得到T(n)=T(n/2)+2T(n/4)cn/2+2cn/4=cn。歸納成功，所以有T(n)=O(n)。(b) T(n)=2T(?n/2?+5)+n解：我們歸納證明，存在一個正數c使得在n≥1時有T(n)￡c(n-10)lg(n–10)。歸納基礎：這樣的正數c在n20時顯然可以找到，使得T(n)￡c(n-10)lg(n–10)。歸納步驟：設存在正數c，當n=1，2，…，k-1（k21）時我們有T(n)￡c(n-10)lg(n–10)。我們證明當n=k時也有T(n)￡c(n-10)lg(n–10)。我們可設c>10。首先，因為k-1≥20，?n/2?10。所以?n/2?+5?n/2?+?n/2?-1k-1。由歸納假設有T(?n/2?+5)￡c[(?n/2?+5)-10]lg[(?n/2?+5)-10]，即T(?n/2?+5)￡c(?n/2?-5)lg(?n/2?-5)。把這個關系代到原遞推關系中，得到T(n)=2T(?n/2?+5)+n￡2c(?n/2?-5)lg(?n/2?-5)+nc(n–10)lg(n/2-5)+n=c(n–10)lg[(n-10)/2]+n=c(n–10)[lg(n-10)-1]+n=c(n–10)lg(n-10)–c(n–10)+n<c(n–10)lg(n-10)–10(n–10)+n<c(n–10)lg(n-10) (因為–10n+100+n=100-9n<0)所以有T(n)￡c(n-10)lg(n–10)=O(nlgn)。證明以下遞推關系有T(n)=O(2n)

:(a) T(n)=nT(n/2)+nT(1)=1。解：我們用歸納法證明，存在正數c>0使得當n1時有T(n)c2n。歸納基礎：我們可假定當n≤5時，存在正數c>1使得T(n)c2n。歸納步驟：假定當n=1，2，…，k-1(k6)時，T(n)c2n。我們證明當n=k時仍有T(n)c2n。由歸納假設，我們有T(n/2)c2n/2。因此，由遞推關系，我們可得：T(n)=nT(n/2)+ncn2n/2+n 很容易觀察到，當n6時，n2n/2–1，我們有T(n)cn2n/2+nc(2n/2–1)2n/2+nc2n–c2n/2+n<c2n (因為n<2n/2和c>1)所以T(n)=O(2n)

。(b) T(n)=T(n-1)+T(n-2)+n2T(1)=1，T(2)=2。解：我們用歸納法證明，存在正數c>0使得當n1時有T(n)c2n。歸納基礎：當n=1和n=2時，取c=5，顯然有T(n)<52n。歸納步驟：假定當n=1，2，…，k-1時，我們有T(n)52n。我們證明當n=k時仍有T(n)52n。由歸納假設，我們有T(n-1)52n-1和T(n-2)52n-2。因此，由遞推關系，我們可得：T(n)=T(n-1)+T(n-2)+n252n-1+52n-2+n2 因為當n>1時，顯然有n252n-2，所以我們有T(n)52n-1+52n-2+n252n-1+52n-2+52n-2=52n歸納成功，所以T(n)=O(2n)

。(c) T(n)=5n2T(n/2)+n3T(1)=1。解：我們用歸納法證明存在正數c>0使得當n1時有T(n)c2n。歸納基礎：我們可假定當n≤30時，存在正數c>1使得T(n)c2n。歸納步驟：假定當n=1，2，…，k-1(k31)時，存在正數c>1使得T(n)c2n。我們證明當n=k時仍有T(n)c2n。由歸納假設，我們有T(n/2)c2n/2，因此，由遞推關系，我們可得：T(n)=5n2T(n/2)+n35n2c2n/2+n3。因為當n>30時，顯然有n32n/2–1，所以，當n>30時，我們有T(n)5n2c2n/2+n3n3c2n/2+n3(2n/2–1)c2n/2+n3c2n–c2n/2+n3c2n (因為n32n/2-1和c>1)所以T(n)=O(2n)

。用序列求和法解以下遞推關系。(a) T(n)=4T(n/2)+n2lgn解：設n=2k，得到T(2k)=4T(2k-1)+22klg2k。令W(k)=T(2k)，得到W(k)=4W(k-1)+k4k。用序列求和法，得到以下演算：W(k)=4W(k-1)+k4k=4[4W(k-2)+(k-1)4(k-1)]+k4k=42W(k-2)+(k-1)4k+k4k =42[4W(k-3)+(k-2)4(k-2)]+(k-1)4k+k4k=... =4kW(0)+4k+24k+...+(k-2)4k+(k-1)4k+k4k=4kW(0)+4k(1+2+...+(k-2)+(k-1)+k)=4kW(0)+4k(k(k+1)/2)=(22kk2)。因為k=lgn，故有T(n)=(n2(lgn)2)。(b) T(n)=3T(n/3)+n解：設n=3k，得T(3k)=3T(3k-1)+3k 用序列求和法，得到以下演算：T(3k)=3T(3k-1)+3=3[3T(3k-2)+3k?1(k?1)=32T(3k-2)+3k(k?1)=...=3kT(30)+3klg3[11+12+…=(3klg3=(nlglgn)。用主方法解以下遞推關系。T(n)=4T(n/2)+nT(n)=4T(n/2)+n2T(n)=4T(n/2)+n3T(n)=7T(n/2)+n2T(n)=4T(n/3)+nT(n)=3T(n/9)+5nT(n)=4T(n/2)+n2n解：(a)a=4,b=2,logba=2。顯然，可令=0.5使f(n)=n=O(n2-)=O(n1.5)。所以T(n)=(n2)。(b)a=4,b=2,logba=2。顯然，f(n)=n2=(nlgba)。所以T(n)=(n2(c)a=4,b=2,logba=2。顯然，可令=0.5使f(n)=n3=(n2+)=(n2.5)。再有af(n/b)=4(n/2)3=0.5n30.5f(n)。所以T(n)=(f(n))=(n3)。(d)a=7,b=2,logba=2.81。因為lgba=log27>2，所以T(n)=Q(nlg2(e)a=4,b=3,logba=1.26。顯然，可令e=0.1>0使f(n)=n=O(n1.26-)。所以有T(n)=Θ(nlogba)=Q((f)a=3,b=9,logba=0.5。因為f(n)=5n=Θ(nlogba)，所以有T(n)=Θ(nlogbalgn)=(n0.5lg(g)a=4,b=2,logba=2。因為f(n)=n2n=n5/2=W(n2+0.1)，再有af(n/b)=4n22n2=12n2ncf(n)，這里cT(n)=Q(f(n))=(n2n)。解遞推關系T(n)=2T(n)+lgn。解：令n=2k，得到T(2k)=2T(2k/2)+k。定義W(k)=T(2k)，我們有如下推導：W(k)=2W(k/2)+k=(klgk)。 因此，T(n)=(klgk)=(lgnlglgn)。證明以下序列和的公式的正確性。(a)k=1nk2k=(n-1)2n+1+2證明：令T(n)=k=1nT(n)=2T(n)-T(n)=k=1nk=[n2n+1+k=2n(k?1)2k]=n2n+1–2-k=2=n2n+1–2–(2n+1–4)=(n-1)2n+1+2。(b)k=1nklgk=(n證明:令T(n)=k=1n首先我們有T(n)=k=1nklgkk=1nklgn=lgnk=1T(n)=k=1nklgkk=n/2nklgkk=n/2n(n2lgn2)n2所以有T(n)=(n2lgn)。*(c)k=2nklgk證明: 令T(n)=k=2nklgk并假定T(n)=k=2nklgk>k=2nkT(n)=k=2nklgk=k=2nklgk+k=n+1<k=2nk<k=2nk<k=2nk<k=2nk+=O(n)+O(n2=O(n2 所以有T(n)=Q(n2lg用積分法證明1k+2k+3k+…+nk=(nk+1)，這里k是任一個固定的正整數。證明： 因為i?1ixkdx<i0nxkdx<i=1n1k+1nk+1<i=1nik<1k+1[(n+因為nk+1=((n+1)k+1)，我們有i=1nik=1k+2k+3k+…+nk=(n假設我們開一部卡車從城市A到城市B，中間一共經過n個蘋果市場，包括城市A和城市B的蘋果市場，并且編號為1到n。在市場i，1≤i≤n，從顧客的觀點看，其每市斤的買入價B[i]和賣出價S[i]都已知，單位是元。下圖給出了一個n=6的例子。現在我們計劃找一個市場i買蘋果，然后再找一個市場ji把蘋果賣掉使得賺的錢最多(如果根本賺不到錢，則使虧損越小越好)。我們假設卡車不可以向回開，并且只做一次買賣。例如，在上面的例子中，最好的方案是在市場4買蘋果而在市場6賣出去，這樣做每斤可賺7-2=5元錢。請設計一個分治算法找出市場i和j使得利潤最大或虧損最小，并分析算法復雜度。解：我們設計一個在市場p到市場r之間進行買賣的最佳解，1prn,然后調用這個算法時置p=1和r=n即可。注意，題目要求ji，所以i=j是允許的。D&C-Max-Apple-Profit(B[],S[],p,r,M,i,j)ifp=r then MS[p]–B[p] //只有一個市場情形 ip jp else q(p+q)/2 D&C-Max-Apple-Profit(B[],S[],p,q,Ml,il,jl) D&C-Max-Apple-Profit(B[],S[],q+1,r,Mr,ir,jr) findleftsuchthatB[left]=min{B[u]|puq} findrightsuchthatS[right]=max{S[u]|q+1ur} McS[right]–B[left] ifMc>max{Ml,Mr} then MMc ileft jright else ifMl>Mr then MMl iil jjl else MMr iir jjr endif endifendifreturn(M,i,j)上面的算法對應的遞推關系是T(n)=T(n/2)+T(n/2)+(n)=(nlgn)。注：上面的算法可改進為O(n)，我們略去討論。假設n個學生S[i]的身高height[i]不同,1≤i≤n，并且已排序為height[1]<height[2]<…<height[n]。另外，他們的性別對應地記錄在數組sex[1..n]中，sex[i]=F表示S[i]是女生，sex[i]=M表示S[i]是男生，1≤i≤n。如果sex[i]=F，sex[j]=M,并且height[i]<height[j],那么S[i]和S[j]可組成一對合格的舞伴。請用分治法設計一個復雜度為O(n)的算法來計算在這n個學生中有多少個不同的合格的配對方案。解：我們用分治法為學生序列S[p..r]設計一個計算配對方案個數的算法，然后調用這個算法時置p=1和r=n即可。這個算法在計算配對方案個數(number-pairs)時，同時算出S[p..r]中有多少個女生和多少個男生。Dancing-pairs(p,r,number-pairs,number-F,number-M) //假設rpifp=r then number-pairs0 //只有一個學生 ifsex[p]=F then number-F1 number-M0 else number-F0 number-M1 endif else q=(p+r)/2 Dancing-pairs(p,q,number-pairs-L,number-F-L,number-M-L) Dancing-pairs(q+1,r,number-pairs-R,number-F-R,number-M-R) number-pairsnumber-pairs-L+number-pairs-R+number-F-Lnumber-M-R number-Fnumber-F-L+number-F-R number-Mnumber-M-L+number-M-RendifEnd算法的復雜度為T(n)=T(n/2)+T(n)+(1)=(n)。給定序列A[1],A[2],…,A[n],請用分治法設計一個復雜度為O(nlgn)的算法來找出其中最長一段遞增(不減)序列段，即找出兩個序號ij,使得A[i]A[i+1]A[i+2]…A[j],并使j-i+1最大。解：我們用分治法為序列A[p..r],p<r,設計一個復雜度為O(nlgn)的算法來找出其中最長遞增序列段，然后調用這個算法時置p=1和r=n即可。Longest-increasing-segment(A[],p,r,d,i,j)//假設rp,A[i]到A[j]是最長遞增序列段，長為d=j-i+1。ifp=r then d1 ijp else q=(p+r)/2 Longest-increasing-segment(A[],p,q,dl,il,jl) Longest-increasing-segment(A[],q+1,r,dr,ir,jr) icq while (ic–1)pandA[ic-1]A[ic] icic–1 endwhile jcq while(jc+1)randA[jc+1]A[jc] jcjc+1 endwhile dcjc–ic+1 ifdcmax{dl,dr} then ddc iic jjc else ifdldr then ddl iil jjl else ddr iir jjr endif endifendifEnd該算法的復雜度為T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。在一條東西方向的大街上有n個人家，它們與西頭的距離順序為H[1]<H[2]<…<H[n]。另外，街上有m個學校，m<n,它們與西頭的距離順序為S[1]<S[2]<…<S[m]。假設每家都有學生，并且步行到最近的學校上學。假設某家與西頭的距離是x,請用分治法設計一個復雜度為O(lgm)的算法來確定這家的學生應該去哪所學校和步行的距離有多遠。請用Nearest-school(S[1..m],k,d,x)作為你的算法的名字。其中，k表示S[k]是要去的學校，d表示從x到S[k]的距離。下面是一個利用(a)中的算法而設計的分治法算法。它確定這n家中哪家學生步行的距離最遠，有多遠，和去哪所學校。調用這個算法時置i=1和j=n即可。請證明這個算法的復雜度是O(nlgm)。Longest-Distance(H[i..j],S[1..m],u,h,dist) //S[u],h和dist是答案,ijifi=j then xH[i] Nearest-school(S[1..m],k,d,x) //調用(a)中的算法 uk hi distd else mid(i+j)/2 Longest-Distance(H[i..mid],S[1..m],u-L,h-L,dist-L) Longest-Distance(H[mid+1..j],S[1..m],u-R,h-R,dist-R) ifdist-L>dist-R then uu-L hh-L distdist-L else uu-R hh-R distdist-R endifendifEnd調用Longest-Distance(H[1..n],S[1..m],u,h,dist)后，我們得到從家h到學校u的距離最遠，該距離為dist。解：(a) 我們考慮學校序列為S[p..r]，算法如下。然后調用這個算法時置p=1和r=m即可。Nearest-school(S[p..r],k,d,x) //p≤r,S[k]和d是答案。ifp=r then kp d|S[k]–x| else mid(p+r)/2 if|S[mid]–x|≤|S[mid+1]–x| thennearest-school(S[p..mid],k,d,x) elsenearest-school(S[mid+1..r],k,d,x) endifendifEnd調用Nearest-school(S[1..m],k,d,x)后，我們得到與x最近的S[k],1km,其距離為d。時間復雜度為T(m)T(m/2)+O(1)=O(lgm).(b)根據算法，我們可得遞推關系時間復雜度為T(n)=T(n/2)+T(n/2)+O(1),T(1)=O(lgm)。用求和法，設n=2k。T(n)=2T(n/2)+O(1)=22T(n/4)+O(1)+O(1)=…=2kT(1)+O(k)=O(nlgm)。*在一條東西方向的大街上有n個人家，它們與西頭的距離順序為H[1]<H[2]<…<H[n]。另外，街上有m個學校，1m<n,它們與西頭的距離順序為S[1]<S[2]<…<S[m]。另外，假設人家H(k),1kn,有U(k)個學生，并且步行到最近的學校上學。為確定起見，如果家兩邊的學校等距離，學生選西邊的學校。請用分治法設計一個復雜度為O(nlgm)的算法來確定哪個學校會接收最多的學生。解：我們假設住家序列為H[u..v]，學校序列為S[i..j]，用分治法來確定哪個學校會接收最多的學生。然后，調用這個算法時，置u=1,v=n,i=1,j=m即可。Serve-most-students(S[i..j],H[u..v],k,p) //學校S[k]會接收最多的學生，人數為p。ifu>v //意味著沒有人家，或者沒有人家離S[i..j]最近 then k0 p0 returnendififi=j then ki pt=u returnendifmid-school(i+j)/2mid-line(S[mid-school]+S[mid-school+1])/2huwhile H[h]≤mid-line hh+1 //找出在mid-line東邊的第一家序號endwhileServe-most-students(S[i..mid-school],H[u..h-1],k1,p1)Serve-most-students(S[mid-school+1,j],H[h..v],k2,p2)ifp1>p2 then kk1 pp1 else kk2 pp2endifEnd調用Serve-most-students(S[1..m],H[1..n],k,p)即可得到答案。算法復雜度可由如下遞歸關系求得：T(n,1)=O(n) T(n,m)=T(n1,m/2)+T(n2,m/2)+cn //c是常數，n1+n2=n。令m=2k，可把遞推關系簡化為：T(n,m)=T(n1,m/2)+T(n2,m/2)+cn我們對m用歸納法證明，存在常數d>c，使得T(n,m)≤dnlgm+d(n+m)。歸納基礎：當m=1時，命題顯然成立。歸納基礎：當m>1時，我們有以下推導： T(n,m)=T(n1,m/2)+T(n2,m/2)+cn≤[dn1lg(m/2)+d(n1+m/2)]+[dn2lg(m/2)+d(n2+m/2)]+cn //由歸納假設=dn1(lgm-1)+d(n1+m/2)+dn2(lgm-1)+d(n2+m/2)+cn=dn1lgm+dn2lgm+dm+cn<dnlgm+d(n+m) 歸納成功。因為m<n，T(n,m)=O(nlgm)。給定序列A[1],A[2],…,A[n],請用分治法設計一個復雜度為O(nlgn)的算法來找出其中一段遞增(不減)序列段，即找出兩個序號ij,使得A[i]A[i+1]A[i+2]…A[j],并使它們的和，k=ij解： 我們用分治法為序列A[p..r]設計一個復雜度為O(nlgn)的算法來找出其中最長遞增序列,然后調用這個算法時置p=1和r=n即可。max-value-increasing-segment(A[p..r],d,i,j)//假設rp,A[i]到A[j]是輸出遞增序列段，其和為d=k=ijifp=r then dA[p] ijp else q=(p+r)/2 Max-value-increasing-segment(A[p..q],dl,il,jl) Max-value-increasing-segment(A[q+1..r],dr,ir,jr) ifA[q]>0 then icq dcA[q] while(ic–1)pandA[ic-1]A[ic]andA[ic-1]>0 icic–1 dcdc+A[ic] endwhile jcq while(jc+1)randA[jc+1]A[jc] jcjc+1 dcdc+A[jc] endwhile else dc- endif ifdcMax{dl,dr} then ddc iic jjc else ifdldr then ddl iil jjl else ddr iir jjr endif endifendifEnd該算法的復雜度為T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。給定序列A[1],A[2],…,A[n],請用分治法設計一個復雜度為O(nlgn)的算法來找出其中兩個序號i<j,使得A[i]A[j],并使它們的和，A[i]+A[j]，最小。如果沒有這樣兩個數，則輸出+∞。解: 這是和書中例題2.9對稱的題目，偽碼如下。 Min-Sum-Two-Numbers(A[p..r],i,j,M) //p≤rifp=r then M+∞ //只有一個數 else mid (p+r)/2 Min-Sum-Two-Numbers(A[p..mid],i1,j1,M1) Min-Sum-Two-Numbers(A[mid+1..r],i2,j2,M2) findi3suchthatA[i3]=min{A[k]|p≤k≤mid} S{A[k]|mid+1≤k≤r,A[i3]≤A[k]} ifS= thenM3+∞ else findj3suchthatA[j3]=min{A[k]|A[k]S} M3A[i3]+A[j3] endif ifM3<M2andM3<M1 then MM3 ii3 jj3 else ifM2<M1 then MM2 ii2 jj2 else MM1 ifM≠+∞ then ii1 jj2 endif endif endifendifEnd當我們調用Max-Sum-Two-Numbers(A[1..n],i,j,M)時，原問題得解。算法復雜度可由下面遞推關系得到：T(n)=2T(n)+O(n)=O(nlgn)。在序列A[1],A[2],…,A[n]中，一個數可能出現若干次。如果一個數出現的次數k超過一半，即k>n/2，那么我們說這個序列有一個壟斷數。請用分治法設計一個復雜度為O(nlgn)的算法來判斷一個給定序列是否有一個壟斷數。如果有，報告這個數及其出現次數k，否則報告k=-。我們約定，該算法只能用比較序列中兩數字是否相同來判斷，比較的結果不報告誰大誰小，只告訴相同或不相同。當比較的兩數字不是序列中數字時，可以報告大小。解: 算法的偽碼如下，正確性顯然。Dominating-number(A[p..r],i,k) //如果有，A[i]出現k>n/2次，否則i=nil，k=-ifp=r then ip k1 else mid (p+r)/2 Dominating-number(A[p..mid],i1,k1) Dominating-number(A[mid+1,r],i2,k2) ifk1- //只有A[i1]和A[i2]可能，檢查之。 then forjmid+1tor ifA[j]=A[i1] then k1k1+1 endif endfor endif ifk2- then forjptomid ifA[j]=A[i2] then k2k2+1 endif endfor endif ifk1>(p-r+1)/2 then ii1 kk1 else ifk2>(p-r+1)/2 then ii2 kk2 else inil k- endif endifendifEnd該算法的復雜度為T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。*每個多米諾骨牌有兩個正整數。假設有n個多米諾骨牌S1,S2,…,Sn水平地放成一排如下例所示。假設我們不能改變骨牌之間相對位置，但可以原地翻轉每個骨牌。我們用L[i]和R[i]分別表示Si(1in)左邊和右邊的數。例如，在下例中L[1]=5,R[1]=8,L[2]=4,R[2]=2等。如果L[i]<R[i]，我們稱Si被置為狀態0并記為W[i]=0，翻轉后則為狀態1并記為W[i]=1。例如下例中S1為狀態0而S2為狀態1。如果L[i]=R[i]，Si的狀態可記為W[i]=0或W[i]=1。請用分治法設計一個算法來確定每個骨牌的狀態使得M=i=1n?1R[i]×L[i+1]取得最大值解: 這題的主要困難在于，如果我們用常規的辦法將序列分為兩半求解，那么兩部分的最佳解合在一起不一定給出全局的最佳解。技巧是，我們把問題稍加修改。我們在原序列中引入兩個非負整數u和v,并確定各骨牌狀態以使得M=u′L[1]+i=1n?1R[i]×L[i+1]+R[n]′v取得最大值。顯然，如果我們能解決這個修改后的問題，那么當我們置u=v=0的話即得出原問題的解。假設S[p,r]表示從Sp到Sr的骨牌序列，下面的分治算法確定這些骨牌的狀態使M=u′L[p]+i=pr?1R[i]×L[i+1]+R[r]′v取得最大值。我們假設Si(1￡i￡n)中兩數字存放在A[i]和B[i]中并且A[i]￡BMax-Value(u,v,S[p,r],W[p,r],m)ifp>r then m?u′v //骨牌序列為空 exitendif q?x?A[q]y?B[q] //中間骨牌的兩個數x和yMax-Value(u,x,S[p,q-1],W1[p,q-1],m1) //x用于左邊序列Max-Value(u,y,S[p,q-1],W2[p,q-1],m2) //y用于左邊序列Max-Value(x,v,S[q+1,r],W3[q+1,r],m3) //x用于右邊序列Max-Value(y,v,S[q+1,r],W4[q+1,r],m4) //y用于右邊序列if(m1+m4)>(m2+m3) //中間骨牌為狀態0時較好 then W[p,q-1]?W1[p,q-1] W[q+1,r]?W4[q+1,r] W[q]?0 m?(m1+m4) else W[p,q-1]?W2[p,q-1] //中間骨牌為狀態1時較好 W[q+1,r]?W3[q+1,r] W[q]?1 m?(m2+m3)endifEnd算法正確性顯然，當我們調用Max-Value(0,0,S[1,n],W[1,n],m)時便得到結果。算法復雜度為T(n)=4T(n?12)+Q(n)=Q(n2第3章 基于比較的排序給出一例證明在最壞情況下，合并算法至少需要n1+n2-1次比較。解：作為一個例子，如果數組A[1..n1]和數組B[1..n2]中數滿足以下條件，那么合并算法需要n1+n2-1次比較:A[1]<A[2]<A[3]<…<A[n1-1]<B[1]<B[2]<B[3]<…<B[n2]<A[n1]。(a) 設計一個復雜度為O(nlgn)的算法以確定數組A[1..n]中的n個數是否有相同的數字。 (b) 設計一個復雜度為O(nlgn)的算法把數組A[1..n]中出現奇數次的數字挑選出來。解：這兩個問題可以用排序來解決。我們假定n2。(a)Repeated-Number(A[1..n])Heap-sort(A[1..n]) //用堆排序對A[1..n]進行排序fori2ton ifA[i]=A[i-1] thenreturn“Yes,A[i]andA[i-1]areidentical.” //報告A[i]和A[i-1]相同 endifendforreturn“Norepeatednumbers.” //沒有重復的數字End因為該算法的大部分時間化在第一步的排序，所以算法復雜度為O(nlgn)。(b)Odd-occurrence(A[1..n])Heap-sort(A[1..n]) //用堆排序對A[1..n]進行排序sA[1] //A[1]是第一個要檢查的數j0 //出現奇數次的數將被按序放入B[1..j]oddtruefori:=2ton ifs=A[i] then ifodd=true thenoddfalse elseoddtrue endif else ifodd=false //A[i]有一個不同的值 then oddtrue sA[i] else jj+1 //odd=true，記錄到B中 B[j]s sA[i] //odd仍然為true，未變 endif endifendforifodd=true //最后一輪中，s=A[n]，此時處理 then jj+1 B[j]s endifreturnB[1..j]End 因為該算法的大部分時間化在第一步的排序，其復雜度為O(nlgn)，而后面步驟所需時間為O(n)，所以算法復雜度為O(nlgn)。(a) 一棵高為h

的堆最少和最多能含有多少個結點(包括所有內結點和葉結點)？ (b) 證明一個含有n個數的堆的高為?lgn?。解

: (a) 當一棵高為h

的堆是一棵滿二叉樹時含有最多的結點。此時的結點數是：Nmax(h)=1+2+22+23...+2h=2h+1–1。 當一棵高為h

的堆的底層只含有一個葉結點時，它含有的結點數最少。此時的結點數是：Nmin(h)=Nmax(h-1)+1=2h。(b) 設一個含有n個數的堆的高為h。從上題(a)可知：Nmin(h)￡n￡Nmax(h)，即2h￡n￡2h+1–1，也就是2h￡n<2h+1。由此可得h￡lgn<h+1。所以有h=?lgn?。假設Heap-Delete(A[1..n],i)表示將A[i]這個數從數組A[1..n]構成的堆中刪去，并使所余n-1個數形成一個堆的操作。用偽碼設計一個復雜度為O(lgn)的算法來實現Heap-Delete(A[1..n],i)(1in)。解：Heap-Delete(A[1..n],i) //1inkey←A[i]A[i]?A[n]n←n–1ifin //如果i=n+1，則已被刪去 then ifkey>A[i] then Max-Heapify(A[1..n],i) else key←A[i] Heap-Increase-Key(A[1..n],i,key) endifendifEnd假設Heap-Decrease-Key(A[1..n],i,key)表示在數組A[1..n]構成的堆中把A[i]的值減少為key，并把A[1..n]修復為一個堆的操作。用偽碼設計一個復雜度為O(lgn)的算法來實現Heap-Decrease-Key(A[1..n],i，key)(1in)。解：Heap-Decrease-Key(A[1..n],i,key) //1inifkey>A[i] thenreturn“error,newkeyislargerthancurrentkey” //錯誤，新值大于現有值endifA[i]?keyMax-Heapify(A[1..n],i)End給定一個排好序的數組A[1]≤A[2]≤…≤A[n]，第2章里例2.1中的二元搜索算法可以用一棵二元搜索樹來描述。樹中每個內結點含有一個數組中的數。樹根里的數是算法進行比較的第一個數，即A[mid]。如果x=A[mid]，則搜索成功并報告。否則，根據結果是x<A[mid]還是x>A[mid]，算法決定是遞歸搜索左半部分，還是遞歸搜索右半部分。因而這棵二元搜索樹的左右兩子樹可相應地遞歸構造。下圖給出了當n=1，2，3，4時二元搜索樹的例子。其中葉結點表示搜索失敗的情況。證明一棵二元搜索樹T的葉結點只出現在最底下二層。證明一棵含n個數的二元搜索樹的高度為h=élg(n+1)ù。解: (a)證明一棵二元搜索樹T的葉結點只出現在最底二層。我們對n進行數學歸納。歸納基礎：當n￡4，上面圖例直接證明了這個結論。歸納步驟： 假設當n=1，2，…，k-1(k>4)時，一棵含n個內結點的二元搜索樹T的葉結點只出現在最底二層。下面我們證明當n=k時結論仍正確。我們分兩種情況證明。n是奇數。在這種情況下，左右兩子樹L和R都含有(n-1)/2個內結點因而形狀完全相同。由歸納假設，它們的葉結點只出現在最底二層。這些葉結點也就是T的葉結點。所以結論正確。n是偶數。在這種情況下，左子樹含(n-2)/2=n/2-1個數字而右子樹含n/2個數字。因為左右子樹都是完全二叉樹，所以左子樹總共含有(n-1)個結點而右子樹含(n+1)個結點(包括葉結點)。右子樹正好比左子樹多二個結點。如果左右兩子樹L和R的高度相等，那么結論得證。故假定他們高度不等。如下圖所示，右子樹比左子樹必定高一層。因為右子樹的底層至少含二個葉子，左子樹必須是一個滿二叉樹，否則它會比右子樹少至少3個結點，不可能。所以左子樹的所有葉子必須在最底層。這就是說，左右子樹的所有葉子都在最底二層。歸納成功。LLRh1h2h1-1證明一棵含n個數的二元搜索樹的高度為h=élog(n+1)ù。證明： 因為一棵含n個數的二元搜索樹有(n+1)個葉子，它總共有2n+1個結點。假設它的高度為h。由(a)部分的解知，它的所有葉子在最底二層。因為底層至少有兩個葉子，但不會多于2h個葉子，所以有(1+2+…+2h-1)+2￡2n+1￡1+2+…+2h-1+2h，即2h+1￡2n+1￡2h+1–1，即(2h+2)￡2n+2￡2h+1。由此得 2h-1+1￡(n+1)￡2h，2h-1<(n+1)￡2hh-1<log(n+1)￡hh-1<élog(n+1)ù￡h。所以有h=élog(n+1)ù。*一個結點在一棵樹中的高度就是以這個結點為根的子樹的高度。證明在一個有n個數字的堆中，高度為h的結點數最多為én2?+1ù證明: 設x是一個有n個數字的堆中高度為h的結點數。我們注意到兩棵高為h的子樹的結點不相交，即一棵高為h的子樹中結點不屬于任一個其他的高為h的子樹。另外，因為所有葉結點都在最底兩層，所有高為h的子樹，最多除一個外，都必定是滿二叉樹。下面的圖清楚地解釋了這一點。唯一可能不是滿二叉樹的子樹唯一可能不是滿二叉樹的子樹一棵高為h的滿二叉樹一共有2h+1-1個結點。而一棵不是滿二叉樹的高為h的子樹，也至少有2h個結點。現在，試想把這x個子樹中除了根以外的結點從T中刪除，剩下的部分是一個有x個葉子的完全二叉樹。這個樹中除葉子外的內結點數正好是(x-1)個。他們正好是T中除高為h的子樹以外的結點集合。所以我們可得以下不等式：n≥(x-1)+(x-1)(2h+1-1)+2h=(x-1)(2h+1)+2h=x(2h+1)-2h+1+2h≥x(2h+1)-2h因此有x≤(n+2h)/(2h+1)=(n/2h+1)+1/2≤én2?+1ù因為x必須是整數，故有x≤én2?+1(K路合并問題) 利用最小堆(min-heap)設計一個時間復雜度為O(nlgk)的算法將k個排好序的序列合并為單一排好序的序列。這里n是所有k個序列中數字的總數。解: 假定A1，A2，...，Ak為k個要合并的序列。假設每個序列已從小到大排好，算法思路如下：首先，把每個序列的頭，A1[1],A2[1],...,Ak[1]，即各序列中最小的數取出并組織為一個最小堆。那么，堆中的根顯然是所有n個數中最小的數。 然后，每次將堆的根中的數取出并放到輸出序列中。根中的數必定是還未輸出的所有數中最小的數。如果根中的數來自序列Aj(1￡j￡k)，那么將根中的數輸出之后，我們把Aj中下一個最小的數，即當前Aj的頭從序列Aj取走放到堆的根結點并將堆修復。如果序列Aj中沒有數字了，那么我們把堆的規模減一并修復。這時參加合并的序列少了一個。因為堆由各序列中最小的數組成，在根中的數顯然是當前還未輸出的所有數中最小的數，算法顯然正確。下面是這個算法的偽碼。我們假定初始時，每個序列至少有一個數字并用一個特殊記號￥表示序列結束。k-Merge(A1,A2,...,Ak)Buildamin-heapH[1..k]fromA1[1],A2[1],...,Ak[1] //由k個序列頭建堆fori?1tok ifH[i]=Aj[1] thenQ[i]?j //記住堆中第i個數是從第j個序列來的。 endifendforforj?1tok head[j]?2 //head[j]是序列Aj中當前剩余部分的首項，即最小數的位置。endfor i?0 //用于輸出序號heap-size?kwhileheap-size10 i?i+1 C[i]?H[1] //C是輸出序列。 j?Q[1] p?head[j] ifAj[p]1￥ then H[1]?Aj[p] head[j]?p+1 else H[1]?H[heap-size] Q[1]?Q[heap-size] Heap-size?heap-size-1 endif ifheap-size>0 thenHeapify(H[1..heap-size],1) //注意，移動H[k]時，Q[k]要相應更新。 endifendwhileEnd因為每輸出一個數之后我們需要修復含有不超過k個元素的堆，其時間為O(lgk)，所以總的時間復雜度為O(nlgk)。大家熟知，數組A[1..n]形成的堆里，第i個數A[i](1≤i≤n)的左兒子、右兒子、及父親的所在位置可以由下面公式算出：Left(A[i])=A[2i]Right(A[i])=A[2i+1]Parent(A[i])=A[?i/2?]但是我們很多時侯不能把這個堆存放在從A[1]開始的數組中，而是存放在從A[p]開始的n個單元中，即存放在A[p..r]中，這里r=p+n–1。這相當于把這n個數在數組中向右平移了(p-1)個位置。請給出在這種情況下，確定數字A[i](p≤i≤r)的左兒子、右兒子、及父親的所在位置的公式。解: 我們把A[p..r]一一對應地映射到另一個數組B[1..n]中，A[i]=B[i-p+1]，p≤i≤r，而B[j]=A[j+p-1]，1≤j≤n。因此新的公式是：Left(A[i])=Left(B[i-p+1])=B[2(i-p+1)]=B[2i-2p+2]=A[2i–p+1]，Right(A[i])=Right(B[i-p+1])]=B[2(i-p+1)+1]=B[2i–2p+3]=A[2i–p+2]，Parent(A[i])=Parent(B[i-p+1])=B[?(i-p+1)/2?]=A[?(i-p+1)/2+p-1]=A[?(i+p-1)/2?]。證明一個有n個數字的堆的左子樹最多含有2n/3個結點。證明: 如下圖所示，我們用L代表左子樹中的結點數，用R代表右子樹中的結點數。在左子樹中，我們用B代表在底層的葉子結點數，而用U代表底層上面的結點數，L=U+B。顯然，我們有關系B≤U+1和U≤R。因而得到L=U+B≤2U+1≤2R+1。因為L+R+1=n，所以R=n–L-1。從而有L≤2R+1≤2(n–L-1)+1=2n-2L-1<2n-2L，也就是L<2n/3，即L2n/3。假設給定一個n個數的數組A[1..n]和一個常數x。我們希望確定數組中是否存在兩個數，A[i]和A[j](1i<jn)，使得A[i]+A[j]=x。設計一個復雜度為O(nlgn)的算法解決這個問題。如果這樣兩個數存在，則報告這兩個數，否則報告不存在。解: 主要思路如下。我們先將數組A[1..n]從左到右排序為A[1]≤A[2]≤A[3]≤…≤A[n]。然后把最小的數和最大的數相加(開始是A[1]和A[n]相加)。如果其和等于x，則問題解決。如果其和小于x，則最小的數不可能在解之中而丟棄。如其和大于x，則最大的數不可能在解之中而丟棄。每次我們從左丟棄一個最小數或從右丟棄一個最大數直至找到答案。Search-SUM(A[1..n]，x)Heap-sort(A[1..n])使得A[1]≤A[2]≤A[3]≤…≤A[n]exist?falsei?1j?nwhilei<jandexist=false ifA[i]+A[j]=x then return(true,i,j) else ifA[i]+A[j]<x theni?i+1 elsej?j-1 endif endifendwhilereturn(nosolution)End因為排序需要O(nlgn)時間而以后的搜索只需要O(n)時間，上面算法的復雜度是O(nlgn)。錦標賽排序法是一個基于比較的排序算法。它可以用一個稱之為錦標賽樹(tournamenttree)的完全二叉樹來描述。這個二叉樹要求正好有n個葉子來存儲n個要排序的數字，并且所有葉子在底層或倒數第2層。下面是一個有5個葉子的一個錦標賽樹圖例。9924710算法開始前，被排序的n個數字被放在這n個葉子中。每個內結點代表一次比較。每次比較中勝者，即較小的數，參加下一輪在其父結點處的比較。在每個內結點處，當它的兩個子結點處的比較有了結果之后，該結點處的比較即可進行。最后，在根結點處的比較決出冠軍，即最小的數。因為一共有(n-1)個內結點，所以只需(n-1)次比較便可以找到最小數。當最小的數被確定后，即可把它送到輸出序列中。另外，把它原來所在的葉子中的值改為。顯然，重復上面的過程可得到下一個最小的數。如果重復所有在內結點處的比較去找下一個最小的數，我們又需要(n-1)次比較。這個復雜度太高。請設計一個只需O(lgn)次比較的算法去找下一個最小的數。(只須解釋步驟，不要求偽碼。)請用偽碼設計一個用數組來實現錦標賽排序的算法，使其復雜度為O(nlgn)。解：在找下一個最小數時，如果我們重復所有在內結點的比較的話，那么，在大部分結點處所比較的兩個數仍然是在找前一個最小數時進行過比較的兩個數，這部分比較不需再做。那么，在哪些結點處所比較的兩個數會有變化呢？容易看出，可能有變化的結點必定是在從前一個最小數所在的葉子到根的這條路徑上。所以我們的算法是，在每個結點處記錄每次比較后誰是勝者、誰是敗者。然后在找下一個最小數時，沿著前一個最小數所在的葉子到根的這條路徑，在每個結點處作一次比較。最后，在根結點處比較的勝者為下一個最小數。因為有n個葉子的這個二叉樹的高度是lgn，所以這條路最長為lgn。因此，找下一個最小的數最多只需lgn-1=O(lgn)次比較。假設要排序的n個數放在數組A[1..n]中。我們用數組W[1..2n-1]來代表錦標賽樹的結點，做法和堆完全一樣。一開始，這n個被排數放在從W[n]到W[2n-1]之中而W[1..n-1]為空。然后從W[n-1]開始到W[1]為止，在每一個內結點處做比較以求得最小數。我們用數組W[1..n-1]記錄各次比較的勝者。排好序的n個數輸出在數組C[1..n]中。在結點W[i]，1in-1，比較的兩個數分別從它兩個子結點的勝者，即W[2i]和W