5. In a max heap, if we increase a key (the value of a node), then...

Transcribed Image Text:

5. In a max heap, if we increase a "key" (the value of a node), then it may invalidate the max heap structure. (a) Draw a heap as an example, and then increase a key's value to show the problem. (b) Write an algorithm (as pseudocode) that fixes this problem with the heap. (c) Demonstrate through an example how your algorithm works. (d) What is the runtime of your algorithm? 6. Using Figure 7.1 as a model, illustrate the operation of PARTITION(A,1,9) on the array A = {3,7,4,2,9,1,8,5,6} 7. Give a brief argument that the running time of PARTITION on a subarray of size n is © (n). 5. In a max heap, if we increase a "key" (the value of a node), then it may invalidate the max heap structure. (a) Draw a heap as an example, and then increase a key's value to show the problem. (b) Write an algorithm (as pseudocode) that fixes this problem with the heap. (c) Demonstrate through an example how your algorithm works. (d) What is the runtime of your algorithm? 6. Using Figure 7.1 as a model, illustrate the operation of PARTITION(A,1,9) on the array A = {3,7,4,2,9,1,8,5,6} 7. Give a brief argument that the running time of PARTITION on a subarray of size n is © (n).

Answer rating: 100% (QA)

Sure I can help you with these questions 5 a Lets start with drawing a max heap and then increase a ... View the full answer