Draw an example of a heap whose keys are all the odd numbers from 1 to 59 (with no repeats), such that the insertion of an entry with key 32 would cause up-heap bubbling to proceed all the way up to a...

Draw an example of a heap whose keys are all the odd numbers from 1 to

59 (with no repeats), such that the insertion of an entry with key 32 would

cause up-heap bubbling to proceed all the way up to a child of the root

(replacing that child’s key with 32).

Describe a sequence of
n
insertions in a heap that requires (nlog
n) time

to process.

Complete Figure 9.9 by showing all the steps of the in-place heap-sort

algorithm. Show both the array and the associated heap at the end of each

step.