Question 1

A binary heap can support a version of deletion in O(log n) time. In this version, you are given a location in the heap to delete. So, the delete instruction is given an index into the array and asked to delete the item in that location. The item that is removed is replaced by the last item in the heap. (We might as well do that since the shape of the heap is completely determined by the number of items). Of course the replacement item might violate the heap property --- i.e., its key may be too small or too large. In this case we may need to "bubble up" or "trickle down" to fix the heap. In may not be obvious that both "bubbling up" and "trickling down" may be needed. In the two binary heaps below, enter numbers in the nodes for a MAX heap so that in the first case, after the key 30 is deleted, the replacement item bubbles up and in the second case, after the key 30 is deleted, the replacement item trickles down. Both heaps have to be MAX heaps (but they, of course, cannot be the same heap). Also, show the resulting heap after deletion. 

First max heap: deleting 30 makes the replacement item bubble up: 30 Result of first heap, after deleting 30: First max heap: deleting 30 makes the replacement item bubble up: 30 Result of first heap, after deleting 30