This is a question with multiple parts and is not two questions posted in one.

Question 4: 1. Say that a pointer p points to an element in the middle of a heap. Give an O(log n) time algorithm to remove this element from the heap. Hint: Its very similar to regular delete.

2. Say that we want to maintain two Heaps one with the minimum at the top (and the children no smaller than the parent) and one with the maximum on the top (and the children no larger than the parent). Thus the operations we want to maintain are Delete Max(H), Delete Min(H) and Insert(H, x). Use two heaps with pointers between two copies of the same elements so that the above operations could be done in O(log n) each. Note that Delete Max, also deletes this item from the Min Heap. Further, this element can be located in the middle of the Min Heap.

Hint: Use part 1 that explains how to delete a vertex from the middle of a Heap.