Chapter 6Michelle Bodnar, Andrew LohrMay 22, 2017Exercise 6.1-1At least 2hand at most 2h+1− 1. Can be seen because a complete binarytree of depth h − 1 has Σh−1i=02i= 2h− 1 elements, and the number of elementsin a heap of depth h is between the number for a complete binary tree of depthh − 1 exclusive and the number in a complete binary tree of depth h inclusive.Exercise 6.1-2Write n = 2m−1+k where m is as large as possible. Then the heap consistsof a complete binary tree of height m − 1, along with k additional leaves alongthe bottom. The height of the root is the length of the longest simple path toone of these k leaves, which must have length m. It is clear from the way wedefined m that m = blg nc.Exercise 6.1-3If there largest element in the subtee were somewhere other than the root,it has a parent that is in the subtree. So, it is larger than it’s parent, so, theheap property is violated at the parent of the maximum element in the subtreeExercise 6.1-4The smallest element must be a a leaf node. Suppose that node x containsthe smallest element and x is not a leaf. Let y denote a child node of x. Bythe max-heap property, the value of x is greater than or equal to the value ofy. Since the elements of the heap are distinct, the inequality is strict. Thiscontradicts the assumption that x contains the smallest element in the heap.Exercise 6.1-5Yes, it is. The index of a child is always greater than the index of the parent,so the heap property is satisfied at each vertex.1Exercise 6.1-6No, the array is not a max-heap. 7 is contained in position 9 of the array, soits parent must be in position 4, which contains 6. This violates the max-heapproperty.Exercise 6.1-7It suffices to show that the elements with no children are exactly indexedby {bn/2c + 1, . . . , n}. Suppose that we had an i in this range. It’s childerenwould be located at 2i and 2i + 1 but both of these are ≥ 2bn/2c + 2 > n and soare not in the array. Now, suppose we had an element with no kids, this meansthat 2i and 2i + 1 are both > n, however, this means that i > n/2. This meansthat i ∈ {bn/2c + 1, . . . , n }.Exercise 6.2-127 17 3 16 13 10 1 5 7 12 4 8 9 027 17 10 16 13 3 1 5 7 12 4 8 9 027 17 10 16 13 9 1 5 7 12 4 8 3 0Exercise 6.2-2Algorithm 1 MIN-HEAPIFY(A,i)1: l = LEF T (i)2: r = RIGHT (i)3: if l ≤ A.heap − size and A[l] < A[i] then4: smallest = l5: else smallest = i6: end if7: if r ≤ A.heap − size and A[r] < A[smallest] then8: smallest = r9: end if10: if smallest 6= i then11: exchange A[i] with A[smallest]12: MIN-HEAPIFY(A, smallest)13: end ifThe running time of MIN-HEAPIFY is the same as that of MAX-HEAPIFY.Exercise 6.2-3The array remains unchanged since the if statement on line line 8 will befalse.2Exercise 6.2-4If i > A.heap − size/2 then l and r will both exceed A.heap − size so theif statement conditions on lines 3 and 6 of the algorithm will never be satisfied.Therefore largest = i so the recursive call will never be made and nothing willhappen. This makes sense because i necessarily corresponds to a leaf node, soMAX–HEAPIFY shouldn’t alter the heap.Exercise 6.2-5Iterative Max Heapify(A, i)while i < A.heap-size dol =LEFT(i)r =LEFT(i)largest = iif l ≤ A.heap-size and A[l] > A[i] thenlargest = lend ifif l ≤ A.heap-size and A[r] > A[i] thenlargest = rend ifif largest 6= i thenexchange A[i] and A[largest]elsereturn Aend ifend whilereturn AExercise 6.2-6Consider the heap resulting from A where A[1] = 1 and A[i] = 2 for2 ≤ i ≤ n. Since 1 is the smallest element of the heap, it must be swappedthrough each level of the heap until it is a leaf node. Since the heap has heightblg nc, MAX-HEAPIFY has worst-case time Ω(lg n).Exercise 6.3-15 3 17 10 84 19 6 22 95 3 17 22 84 19 6 10 95 3 19 22 84 17 6 10 95 84 19 22 3 17 6 10 984 5 19 22 3 17 6 10 984 22 19 5 3 17 6 10 984 22 19 10 3 17 6 5 93Exercise 6.3-2If we had started at 1, we wouldn’t be able to guarantee that the max-heapproperty is maintained. For example, if the array A is given by [2,1,1,3] thenMAX-HEAPIFY won’t exchange 2 with either of it’s children, both 1’s. How-ever, when MAX-HEAPIFY is called on the left child, 1, it will swap 1 with 3.This violates the max-heap property because now 2 is the parent of 3.Exercise 6.3-3All the nodes of height h partition the set of leaves into sets of size between2h−1+ 1 and 2h, where all but one is size 2h. Just by putting all the childrenof each in their own part of trhe partition. Recall from 6.1-2 that the heap hasheight blg(n)c, so, by looking at the one element of this height (the root), weget that there are at most 2blg(n)cleaves. Since each of the vertices of height hpartitions this into parts of size at least 2h−1+ 1, and all but one correspondsto a part of size 2h, we can let k denote the quantity we wish to bound, so,(k − 1)2h+ k(2h−1+ 1) ≤ 2blg(n)c≤ n/2sok ≤n + 2h2h+1+ 2h+ 1≤n2h+1≤ln2h+1mExercise 6.4-145 13 2 25 7 17 20 8 45 13 20 25 7 17 2 8 45 25 20 13 7 17 2 8 425 5 20 13 7 17 2 8 425 13 20 5 7 17 2 8 425 13 20 8 7 17 2 5 44 13 20 8 7 17 2 5 2520 13 4 8 7 17 2 5 2520 13 17 8 7 4 2 5 255 13 17 8 7 4 2 20 2517 13 5 8 7 4 2 20 252 13 5 8 7 4 17 20 2513 2 5 8 7 4 17 20 2513 8 5 2 7 4 17 20 254 8 5 2 7 13 17 20 258 4 5 2 7 13 17 20 258 7 5 2 4 13 17 20 254 7 5 2 8 13 17 20 257 4 5 2 8 13 17 20 252 4 5 7 8 13 17 20 255 4 2 7 8 13 17 20 252 4 5 7 8 13 17 20 254 2 5 7 8 13 17 20 252 4 5 7 8 13 17 20 25Exercise 6.4-2We’ll prove the loop invariant of HEAPSORT by induction:Base case: At the start of the first iteration of the for loop of lines 2-5 wehave i = A.l ength. The subarray A[1..n] is a max-heap since BUILD-MAX-HEAP(A) was just called. It contains the n smallest elements, and the emptysubarray A[n+1..n] trivially contains the 0 largest elements of A in sorted order.Suppose that at the start of the ithiteration of of the for loop of lines 2-5,the subarray A[1..i] is …
View Full Document
Unlocking...