Mark Allen Weiss 数据结构与算法分析 课后习题答案6.pdf

Chapter6:PriorityQueues(Heaps)6.1Yes.When an element is inserted,we compare it to the current minimum and change theminimum if the new element is smaller.DeleteMin?operations are expensive in thisscheme.6.21326754151412910111381321264815149751113106.3The result of three DeleteMins,?starting with both of the heaps in Exercise 6.2,is as fol-lows:4651371081514129114651271081514913116.46.5 These are simple modifications to the code presented in the text and meant as programmingexercises.6.6225.To see this,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-6.7(a)We show that H?(N?),which is the sum of the heights of nodes in a complete binary treeof N?nodes,is N?b?(N?),where b?(N?)is the number of ones in the binary representation ofN?.Observe that for N?=0 and N?=1,the claim is true.Assume that it is true for values ofk?up to and including N?1.Suppose the left and right subtrees have L?and R?nodes,respectively.Since the root has height?log 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.If it is in the left subtree,then the right subtree is a perfect tree,andb?(R?)=?log N?1.Further,the binary representation of N?and L?are identical,with theexception that the leading 10 in N?becomes 1 in L?.(For instance,if N?=37=100101,L?=10101.)It is clear that the second digit of N?must be zero if the last node is 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 representation of R?is 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-parisons and generates ordering information indicated by the binomial tree shown here.abcdefghThe eighth comparison is between b?and c?.If c?is less than b?,then b?is made a child of c?.Otherwise,both c?and d?are made children of b?.(c)A recursive strategy is used.Assume that N?=2k?.A binomial tree is built for the N?elements as in part(b).The largest subtree of 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 another binomial tree of 2k?1elements.At that point,the root has a sub-tree that is a heap of 2k?1 1 elements and another subtree that is a binomial tree of 2k?1elements.Recursively convert that subtree into a heap;now the whole structure is a binaryheap.The running time for N?=2k?satisfies T?(N?)=2T?(N?/2)+log N?.The base case isT?(8)=8.-30-6.8Let D?1,D?2,.,Dk?be random variables representing the depth of the smallest,second smal-lest,and k?th?smallest elements,respectively.We are interested in calculating E?(Dk?).Inwhat follows,we assume that the heap size N?is one less than a power of two(that is,thebottom level is completely filled)but sufficiently large so that terms bounded by O?(1/N?)are negligible.Without loss of generality,we may assume that the k?th?smallest element isin the left subheap of the root.Let p?j?,k?be the probability that this element is the?j?th?smal-lest element in the subheap.Lemma:For k?1,E?(Dk?)=?j?=1k?1p?j?,k?(E?(D?j?)+1).Proof:An element that is at depth d?in the left subheap is at depth d?+1 in the entiresubheap.Since E?(D?j?+1)=E?(D?j?)+1,the theorem follows.Since by assumption,the bottom level of the heap is full,each of second,third,.,k?1th?smallest elements are in the left subheap with probability of 0.5.(Technically,the probabil-ity should be 12 1/(N?1)of being in the right subheap and 12+1/(N?1)of being in theleft,since we have already placed the k?th?smallest in the right.Recall that we have assumedthat terms of size O?(1/N?)can be ignored.)Thusp?j?,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 the assumption that it holds for all smaller k?.Now,by the inductive hypothesis,for any 1?j?k?1,E?(D?j?)+E?(Dk?j?)log?j?+log k?j?Since?f?(x?)=log x?is convex for x?0,log?j?+log k?j?2log(k?/2)ThusE?(D?j?)+E?(Dk?j?)log(k?/2)+log(k?/2)Furthermore,since p?j?,k?=pk?j?,k?,p?j?,k?E?(D?j?)+pk?j?,k?E?(Dk?j?)p?j?,k?log(k?/2)+pk?j?,k?log(k?/2)From the lemma,E?(Dk?)=?j?=1k?1p?j?,k?(E?(D?j?)+1)=1+?j?=1k?1p?j?,k?E?(D?j?)ThusE?(Dk?)1+?j?=1k?1p?j?,k?log(k?/2)-31-1+log(k?/2)?j?=1k?1p?j?,k?1+log(k?/2)log k?completing the proof.It can also be shown that asymptotically,E?(Dk?)log(k?1)0.273548.6.9(a)Perform a preorder traversal of the heap.(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-case inputs,but also on random data.6.12(a)If the heap is organized as a(min)heap,then starting at the hole at the root,find a pathdown to a leaf by taking the minimum child.The requires roughly log N?comparisons.Tofind the correct place where to move the hole,perform a binary search on the log N?ele-ments.This takes O?(log log N?)comparisons.(b)Find a path of minimum children,stopping after log N?log log N?levels.At this point,it is easy to determine if the hole should be placed above or below the stopping point.If itgoes below,then continue finding the path,but perform the binary search on 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 search on the first log N?log log N?elements.The binary searchtakes at most log log N?comparisons,and the path finding took only log N?log log N?,sothe total in this case is log N?.So the worst case is the first case.(c)The bound can be improved to log N?+log*N?+O?(1),where log*N?is the inverse Ack-erman function(see Chapter 8).This bound can be found 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?)logd?N?).(b)O?(M?+N?)log N?).(c)O?(M?+N?2).(d)d?=max(2,M?/N?).(See the related discussion at the end of Section 11.4.)-32-6.16311891041585211162121118176.171237654891011121314156.18 This theorem is true,and the proof is very much along the same lines as Exercise 4.17.6.19 If elements are inserted in decreasing order,a leftist heap consisting of a chain of left chil-dren is formed.This is the best because the right path length 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 the obvious solution doesnt work.However,we canstill do the operation efficiently 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 mightcreate an imbalance for nodes on the path from x?s parent to the root that would need to befixed by a child swap.However,it is easy to show that at most log N?nodes can be affected,preserving the time bound.This is discussed in Chapter 11.6.21 Lazy deletion in leftist heaps is discussed in the paper by Cheriton and Tarjan 9.The gen-eral idea is that if the root is marked deleted,then a preorder traversal of the heap is formed,and the frontier of marked nodes is removed,leaving a collection of heaps.These can bemerged two at a time by placing all the heaps on a queue,removing two,merging them,andplacing the result at the end of the queue,terminating when only one heap remains.6.22(a)The standard way to do this is to divide the work into passes.A new pass begins whenthe first element reappears in a heap that is dequeued.The first pass takes roughly-33-2*?1*?(N?/2)time units because there are N?/2 merges of trees with one node each on theright path.The next pass takes 2*?2*?(N?/4)time units because of 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 so on.The sum converges to 4N?.(b)It generates heaps that are more leftist.6.23311891041585211162121118176.241327564151113914101286.25 This claim is also true,and the proof is similar in spirit to Exercise 4.17 or 6.18.6.26 Yes.All the single operation estimates in Exercise 6.22 become amortized instead ofworst-case,but by the definition of amortized analysis,the sum of these estimates is aworst-case bound for the sequence.6.27 Clearly the claim is true for k?=1.Suppose it is true for all values i?=1,2,.,k?.A Bk?+1tree is formed by attaching a Bk?tree to the root of a Bk?tree.Thus by induction,it containsa B?0through Bk?1tree,as well as the newly attached Bk?tree,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 Bk?tree to the original Bk?tree.The original-34-thus had(dk)nodes at depth d?.The attached tree had(d?1k)nodes at depth d?1,which are now at depth d?.Adding these two terms and using a well-known formula estab-lishes the theorem.6.29413152318246551122124651426161822955116.30 This is established in Chapter 11.6.31 The algorithm is to do nothing special merely Insert?them.This is proved in Chapter 11.6.35 Dont keep the key values in the heap,but keep only the difference between the 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 first bound is O?(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 first bound is better.Whenk?=(N?),the bounds are identical.-35-