To see why there can be no heap of size seven which would give a sorted sequence on being postorder or inorder traversed we only have to observe that the root is never the first element of the traversal sequence in these two traversal methods and the root is smaller than all its children and their children and so on (not smaller than equal to because the elements are distinct) so the traversal sequence is not in correct order.
R-6.5: To just outline the proof here, we can see that the sum of log 1 to log n is the same as log (1.2.3...n) ie. log(n!). Using Stirlings approximation we can show that n! >= n^n whence the result follows.
R-6.7: To remove key 16 from the heap of Fig 6.3 we do the
following:
1. Swap 16 with the root (4).
2. Delete 16 by swapping with the last element (8) and bubbling 8
down.
3. Bubble 4 up.
R-6.8: To replace 5 with 18 in the heap of Fig 6.3 we do the
following:
1. Find key 5 and overwrite it with 18.
2. Since 18 is larger than the root (4) and larger than its children
(15, 9), bubble it downwards like you would in the removal method.
Note: Although I am not giving the diagrams for R-6.7 and R-6.8 here, it is expected that you would draw them in your submission.
C-6.6: To report all the keys smaller than some query key x we would first compare the root of the heap with x. If it is larger than x then the algorithm terminates else we report it and perform the same operation on both its children recursively. We can see that this algorithm will perform k comparisons at least. But at each node that it reports it may perform 2 comparisons extra with the children of that node which may be larger than x. This means that it will perform upto 3k comparisons at most which is O(k).