(a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9,...

 

Transcribed Image Text:

(a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time and in the giver order, into an initially empty binary min heap. (b) Show the result of performing three deleteMin operations in the heap of the previous binary min heap. (c) Write a method replaceKey in the MinHeap class with the following signature: public void replaceKey(Integer oldKey, Integer newKey) The method will replace the first occurrence of oldKey with the newKey, and restore the Min-Heap property after the change. If the oldKey does not exist in the heap, the method prints an appropriate message and returns without changing the heap. Example: Suppose our binary heap object (bh) has the following keys: *** 4 6 7 32 19 64 26 99 42 54 28 Then the method call: bh.replaceKey (oldKey Integer(54), newKey Integer(2)) should change the keys to: *** 2 4 7 32 6 64 26 99 42 19 28 Note: You can assume that the methods perlocateUp and perlocateDown are already implemented in your MinHeap class. (d) What is the running time complexity of your replaceKey method? Justify (e) Consider an initially empty max-heap, where the following keys are to be inserted one at a time: 11, 19, 23, 12, 13, 17, 13, 14, 18, and 33. Draw the tree that results after building this max-heap. (f) Is it possible to find the maximum in a min-heap with N integer nodes in O(logn) time? Justify. Important Notes: For this problem, you have only one Java implementation in part (c). In this part you need to submit only the implementation of the replaceKey method. For parts (a), (b), and (e) of this problem, you must draw the min (or max) heaps using the appropriate graphics tools at your convenience. Heaps that were drawn by hand will be not accepted. (a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time and in the giver order, into an initially empty binary min heap. (b) Show the result of performing three deleteMin operations in the heap of the previous binary min heap. (c) Write a method replaceKey in the MinHeap class with the following signature: public void replaceKey(Integer oldKey, Integer newKey) The method will replace the first occurrence of oldKey with the newKey, and restore the Min-Heap property after the change. If the oldKey does not exist in the heap, the method prints an appropriate message and returns without changing the heap. Example: Suppose our binary heap object (bh) has the following keys: *** 4 6 7 32 19 64 26 99 42 54 28 Then the method call: bh.replaceKey (oldKey Integer(54), newKey Integer(2)) should change the keys to: *** 2 4 7 32 6 64 26 99 42 19 28 Note: You can assume that the methods perlocateUp and perlocateDown are already implemented in your MinHeap class. (d) What is the running time complexity of your replaceKey method? Justify (e) Consider an initially empty max-heap, where the following keys are to be inserted one at a time: 11, 19, 23, 12, 13, 17, 13, 14, 18, and 33. Draw the tree that results after building this max-heap. (f) Is it possible to find the maximum in a min-heap with N integer nodes in O(logn) time? Justify. Important Notes: For this problem, you have only one Java implementation in part (c). In this part you need to submit only the implementation of the replaceKey method. For parts (a), (b), and (e) of this problem, you must draw the min (or max) heaps using the appropriate graphics tools at your convenience. Heaps that were drawn by hand will be not accepted.