2022年MarkAllenWeiss数据结构与算法分析课后习题答案 .pdf

Chapter6:PriorityQueues(Heaps)6.1Yes. When an element is inserted, we compare it to the current minimum and change theminimumifthe new element is smaller.DeleteMinoperations are expensive in thisscheme.6.21326754151412910111381321264815149751113106.3The result of three DeleteMins, starting with both of the heapsin Exercise 6.2, is as fol-lows:4651371081514129114651271081514913116.46.5Theseare simple modi?cations to the code presentedin the text and meant asprogrammingexercises.6.6225. To seethis, start with i =1 and position at the root. Follow the path toward the lastnode, doubling i when taking a left child, and doubling i and adding one when taking aright child.-29-名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 6.7(a) We show that H (N ), which is the sum of the heights of nodesin a complete binary treeof N nodes,is N - b(N), where b(N ) is the number of ones in the binary representationofN . Observe that for N = 0 and N = 1, the claim is true. Assume that it is true for valuesofk up to and including N - 1. Suppose the left and right subtrees have L and R nodes,respectively. Since the root hasheightlog N , we haveH (N ) =log N+ H (L ) + H (R)=log N+ L - b (L ) + R - b (R)= N - 1 + (log N- b(L ) - b(R)The second line follows from the inductive hypothesis, and the third follows becauseL + R = N - 1. Now the last node in the tree is in either the left subtree or the right sub-tree.Ifitis intheleftsubtree, then the rightsubtree isaperfect tree, andb(R) =log N- 1. Further, the binary representationof N and L are identical, with theexception that the leading 10 in N becomes1 in L . (For instance,if N = 37 = 100101, L =10101.) It is clear that the seconddigit of N must be zero if the last nodeis in the left sub-tree. Thus in this case,b(L) = b(N ), andH (N ) = N - b (N )If the last node is in the right subtree,then b(L ) =log N . The binary representationof Ris identical to N , except that the leading 1 is not present. (For instance,if N = 27 = 101011,L = 01011.) Thus b(R) = b (N ) - 1, and againH (N ) = N - b (N )(b) Run a single-elimination tournament among eight elements. This requires seven com-parisonsand generatesordering information indicated by thebinomial tree shown here.abcdefghThe eighth comparison is betweenb and c. If c is less than b, then b is madeachild of c.Otherwise, both c and d aremadechildren of b.(c) A recursive strategy is used. Assume that N = 2k. A binomial tree is built for the Nelements asin part (b). The largest subtreeof the root is then recursively converted into abinary heap of 2k- 1elements. The last element in the heap (which is the only one on anextra level) is then inserted into the binomial queue consisting of the remaining binomialtrees,thus forming anotherbinomial tree of 2k- 1elements. At that point, theroot hasasub-tree that is a heap of 2k- 1- 1 elements and another subtree that is a binomial tree of 2k- 1elements. Recursively convert that subtreeinto aheap; now the whole structure is abinaryheap. The running time for N = 2ksatis?es T(N) = 2T (N / 2) + log N. The base case isT(8) = 8.-30-名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 6.8Let D1, D2, ., Dkbe random variables representingthe depth of the smallest,secondsmal-lest, and kthsmallest elements, respectively. We are interested in calculating E (Dk). Inwhat follows, we assumethat the heapsize N is one less than a power of two (that is, thebottom level is completely ?lled) but suf?ciently large so that terms bounded by O (1 / N)are negligible.Without loss of generality, we may assumethat the kthsmallest element isin the left subheapof the root. Let pj,kbe the probability that this element is the jthsmal-lest elementin the subheap.Lemma: For k1, E (Dk) =j=1k- 1pj ,k(E(Dj) + 1).Proof: An element that is at depth d in the left subheap is at depth d + 1 in the entiresubheap. Since E (Dj+ 1) = E(Dj) + 1, thetheorem follows.Since by assumption, the bottom level of the heap is full, each of second,third, ., k- 1thsmallest elementsarein the left subheapwith probability of 0.5. (Technically, the probabil-ity should be ?12- 1/(N - 1) of being in the right subheapand ?12+ 1/(N - 1) of being in theleft, since we have already placed the kthsmallest in theright. Recall that we haveassumedthat terms of size O (1/N ) can be ignored.) Thuspj,k= pk- j,k=2k- 21_(j - 1k - 2)Theorem: E (Dk) log k .Proof: The proof is by induction.The theorem clearly holds for k = 1 and k = 2. We thenshow that it holds for arbitrary k 2 on theassumption that it holds for all smaller k. Now,by the inductive hypothesis, for any 1 j k- 1,E (Dj) + E(Dk- j) log j + log k- jSince f (x) = log x is convex for x 0,log j + log k- j 2log (k / 2)ThusE (Dj) + E(Dk - j) log (k/ 2) + log (k/ 2)Furthermore, sincepj ,k= pk - j ,k,pj,kE (Dj) + pk- j,kE (Dk- j) pj ,klog (k/ 2) + pk- j,klog (k/ 2)From the lemma,E (Dk) =j =1k- 1pj,k(E (Dj) + 1)= 1 +j =1k- 1pj ,kE (Dj)ThusE (Dk) 1 +j =1k- 1pj ,klog (k/ 2)-31-名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 1 + log (k/ 2)j=1k- 1pj,k1 + log (k/ 2)log kcompleting the proof.It can also be shown that asymptotically, E (Dk) log (k- 1) - 0.273548.6.9(a) Perform apreorder traversalof theheap.(b) Works for leftist and skew heaps. The running time is O(Kd ) for d-heaps.6.11 Simulations show that the linear time algorithm is the faster, not only on worst-caseinputs,but also on random data.6.12 (a) If the heapis organized asa (min) heap,then starting at the hole at the root, ?nd apathdown to a leaf by taking the minimum child. The requires roughly log N comparisons. To?nd the correct place where to move the hole, perform a binary search on the log N ele-ments. This takesO (log log N) comparisons.(b) Find apath of minimum children, stopping after log N - log log N levels. At this point,it is easyto determine if the hole should be placed above or below the stopping point. If itgoes below, then continue ?nding the path, but perform the binary searchon only the lastlog log N elements on the path, for a total of log N + log log log N comparisons. Other-wise, perform a binary searchon the ?rst log N - log log N elements. The binary searchtakes at most log log N comparisons, and the path ?nding took only log N - log log N , sothe total in this caseis log N. So the worst caseis the?rst case.(c) The bound can be improved to log N + log*N + O(1), where log*N is theinverse Ack-ermanfunction (seeChapter8). This bound can befound in reference16.6.13 The parent is at position(i + d - 2)/d . The children are in positions (i - 1)d + 2, .,id + 1.6.14 (a) O(M + dN)logdN ).(b) O(M + N)log N).(c) O(M + N2).(d) d= max (2, M / N ).(Seethe related discussion at the end of Section 11.4.)-32-名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 6.16311891041585211162121118176.171237654891011121314156.18 This theorem is true, and the proof is very much along thesamelines asExercise 4.17.6.19 If elementsare inserted in decreasingorder, a leftist heapconsisting of a chain of left chil-dren is formed. This is thebest becausetheright pathlength is minimized.6.20 (a) If a DecreaseKey is performed on a node that is very deep(very left), the time to per-colate up would be prohibitive.Thus theobvious solution doesntwork. However, we canstill do the operation ef?ciently by a combination of Delete and Insert . To Delete an arbi-trary node x in the heap,replace x by the Merge of its left and right subheaps. This mightcreatean imbalance for nodeson the path from xsparent to the root that would need to be?xed by achild swap. However, it is easyto show that at most log N nodescanbe affected,preserving the time bound. This is discussedin Chapter11.6.21 Lazy deletion in leftist heapsis discussedin the paperby Cheriton and Tarjan 9. The gen-eral idea is that if the root is marked deleted,thena preorder traversalof the heapis formed,and the frontier of marked nodes is removed, leaving a collection of heaps.These can bemerged two at atime by placing all the heapson a queue,removing two, merging them, andplacing the result at the end of the queue,terminating when only one heapremains.6.22 (a) The standardway to do this is to divide the work into passes. A new passbegins whenthe ?rst element reappears in a heap that is dequeued. The ?rst pass takes roughly-33-名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 2* 1* (N/ 2) time units becausethere are N / 2 merges of trees with one node each on theright path. The next passtakes 2* 2* (N / 4) time units becauseof the roughly N / 4 mergesof trees with no more than two nodes on the right path. The third pass takes 2* 3* (N/ 8)time units, and soon. The sum convergesto 4N .(b) It generatesheapsthat aremore leftist.6.23311891041585211162121118176.241327564151113914101286.25 This claim is also true, and the proof is similar in spirit to Exercise4.17 or 6.18.6.26 Yes.Allthe single operation estimates in Exercise 6.22 become amortized instead ofworst-case, but by the de?nition of amortized analysis, the sum of these estimates is aworst-casebound for the sequence.6.27 Clearly the claim is true for k = 1. Supposeit is true for all values i = 1, 2, ., k. A Bk+1tree is formed by attaching a Bktree to the root of a Bktree. Thus by induction, it containsaB0through Bk- 1tree,aswell asthe newly attachedBktree, proving the claim.6.28 Proof is by induction. Clearly the claim is true for k = 1. Assume true for all values i = 1,2, ., k. A Bk+1tree is formed by attaching a Bktree to the original Bktree. The original-34-名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - thus had(dk)nodes at depth d. The attached tree had(d- 1k)nodes at depth d- 1,which arenow at depth d. Adding thesetwo terms and using awell-known formula estab-lishesthe theorem.6.29413152318246551122124651426161822955116.30 This is establishedin Chapter 11.6.31 The algorithm is to do nothing special - merely Insert them. This is proved in Chapter11.6.35 Dontkeep the key valuesin the heap,but keep only the difference betweenthe value of thekey in a node and the value of the key in its parent.6.36 O (N + k log N)is a better bound than O (N log k).The ?rstbound isO(N ) ifk = O(N / log N).The second bound is more than this as soon as k grows faster than aconstant. For the other values ? (N / log N ) = k = (N ), the ?rst bound is better. Whenk = (N), the bounds areidentical.-35-名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -