《Mark Allen Weiss 数据结构与算法分析 课后习题答案6》由会员分享，可在线阅读，更多相关《Mark Allen Weiss 数据结构与算法分析 课后习题答案6（7页珍藏版）》请在金锄头文库上搜索。
1、Chapter 6: Priority Queues (Heaps) 6.1 Yes. When an element is inserted, we compare it to the current minimum and change the minimum if the new element is smaller. DeleteMin operations are expensive in this scheme. 6.2 1 3 2 6 7 5 4 15 14 12 9 10 11 13 8 1 3 2 12 6 4 8 15 14 9 7 5 11 13 10 6.3 The r
2、esult of three DeleteMins, starting with both of the heaps in Exercise 6.2, is as fol- lows: 4 6 5 13 7 10 8 15 14 12 9 11 4 6 5 12 7 10 8 15 14 9 13 11 6.4 6.5 These are simple modications to the code presented in the text and meant as programming exercises. 6.6 225. To see this, start with i =1 an
3、d position at the root. Follow the path toward the last node, doubling i when taking a left child, and doubling i and adding one when taking a right child. -29-6.7 (a) We show that H (N ), which is the sum of the heights of nodes in a complete binary tree of N nodes, is N - b (N ), where b (N ) is t
4、he number of ones in the binary representation of N . Observe that for N = 0 and N = 1, the claim is true. Assume that it is true for values of k 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 have H (N ) = log N
5、+ 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 because L + 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
6、, then the right subtree is a perfect tree, and b (R ) = log N - 1. Further, the binary representation of N and L are identical, with the exception that the leading 10 in N becomes 1 in L . (For instance, if N =3 7=100101, L = 10101.) It is clear that the second digit of N must be zero if the last n
7、ode is in the left sub- tree. Thus in this case, b (L ) = b (N ), and H (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 =2 7=101011, L = 01011.) Thus b (
8、R ) = b (N ) - 1, and again H (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. a b c d e f g h The eighth comparison is between b and c.I f c is less than b
9、, 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 = 2 k . A binomial tree is built for the N elements as in part (b). The largest subtree of the root is then recursively converted into a binary heap of 2 k - 1 elements. T
10、he last element in the heap (which is the only one on an extra level) is then inserted into the binomial queue consisting of the remaining binomial trees, thus forming another binomial tree of 2 k - 1 elements. At that point, the root has a sub- tree that is a heap of 2 k - 1- 1 elements and another
11、 subtree that is a binomial tree of 2 k - 1 elements. Recursively convert that subtree into a heap; now the whole structure is a binary heap. The running time for N = 2 k satises T (N ) = 2T (N / 2) + log N . The base case is T (8) = 8. -30-6.8 Let D 1 , D 2 , ., D k be random variables representing
12、 the depth of the smallest, second smal- lest, and k th smallest elements, respectively. We are interested in calculating E (D k ). In what follows, we assume that the heap size N is one less than a power of two (that is, the bottom level is completely lled) but sufciently large so that terms bounde
13、d by O (1 / N ) are negligible. Without loss of generality, we may assume that the k th smallest element is in 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 (D k ) = j =1 S k - 1 p j ,k (E (D j ) + 1). Pr
14、oof: An element that is at depth d in the left subheap is at depth d + 1 in the entire subheap. 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 - 1 th smallest elements are in the left subheap with probabil
15、ity of 0.5. (Technically, the probabil- ity should be 1 2 - 1/(N - 1) of being in the right subheap and 1 2 + 1/(N - 1) of being in the left, since we have already placed the k th smallest in the right. Recall that we have assumed that terms of size O (1/N ) can be ignored.) Thus p j ,k = p k - j ,k = 2 k - 2 1 _ _ ( j - 1 k - 2) Theorem: E (D k ) log k . Proof: The proof is by induction. The theorem clearly holds for k = 1 and k = 2. We then show that it holds for arbitrary k 2 on the assumption that it h
