Data Structures and Algorithms.

Answer needs to be in JAVA

Make sure to include the proper algorithm for the deletMin and deletemax operations.

Do all the parts of the problem including any analysis and proofs using method of induction as needed.

Support your algorithm with the code and proper documentation.

Include proper O-notation analysis and at least 2 sample runs to ensure working of all methods.

6.18 A min-max heap is a data structure that supports both deleteMin and deleteMax in O(log N) per operation. The structure is identical to a binary heap, but the heap- order property is that for any node, X, at even depth, the element stored at X is smaller than the parent but larger than the grandparent (where this makes sense), and for any node X at odd depth, the element stored at X is larger than the parent but smaller than the grandparent. See Figure 6.57 a. How do we find the minimum and maximum elements? *b. Give an algorithm to insert a new node into the min-max heap. *c. Give an algorithm to perform deleteMin and deleteMax. *d. Can you build a min-max heap in linear time: H*e. Suppose we would like to support deleteMin, deleteMax, and merge. Propose a data structure to support all operations in O(log N) time