Implement a data structure to keep track of median, maximum and minimum and report them in O(1) time. The data structure has to support efficient insertion, and it needs to also support search and remove. These requirements can be handled easily by using two binary heaps: a max heap and a min heap. Our intention is to store half of the numbers in the max heap and the other half in the min heap.Also all numbers in the max heap be smaller than the numbers in the min heap. In such an arrangement, the median will be either the root of the max heap or the root of the min heap. When we insert more items in this data structure, we can compare the item with the current median. If it is smaller than the current median then we would store it in the max heap. Otherwise, it should go in the min heap. Requirement : the sizes of the max heap and min heap should never differ by more than one. To "rebalance" our heaps when one heap has two more items than the other heap, we simply remove the root of the larger heap and insert it in the other heap. The remove operation we want to support in this data structure looks for a particular item and deletes it from the heap. The search takes O(n) time but the actual deletion from the heap takes O(log n) time. The complication is that whenever you remove an item from our data structure, you have to check if you happen to have removed the minimum or the maximum item. If that is the case, you have to go and find the new minimum or new maximum item, so that the data structure can continue to report the minimum and maximum in O(1) time. This search for new minimum/maximum will take O(n) which should be considered very slow. The implementation must be templated and is required to use only one binary heap implementation that works for both min heaps and max heaps using function pointers. you want to have function pointers that compare two items. The idea is that code for a min heap and a max heap are identical except you need to know what "less than" means. So, if you have a function pointer that points to a function that does the comparison, you can write the same code that works for both a min heap and a max heap. Your assignment is to implement the MedianHeap data as described above. No header files are provided so you are free to design your own C++ classes, subject to the requirements below. The name of the class must be MedianHeap. You must also have a separate class called Heap. The MedianHeap class must use two Heap data members: a min heap and a max heap. The Heap implementation must be array based and start at index 1. (Just leave index 0 unused.) Both MedianHeap and Heap must be templated and work with base C++ types (e.g., int and float) and any well-implemented classes. The Heap class must store function pointers to comparison functions and use the function pointers to invoke functions that compare the data items. In particular, it should not assume that the template parameters are instantiated with types that have <, <=, ==, >= and > defined. No STL container classes may be used in this programming project. In particular, you may not use vector instead of an array in your Heap class. Specific requirement : Constructor with the signature : template MedianHeap::MedianHeap( bool (*lt) (const T&, const T&), bool (*gt) (const T&, const T&), int cap=100 ) ; The first function returns true if the first parameter is less than the second parameter. The second function returns true if the first parameter is greater than the second. The constructor must create a MedianHeap object capable of holding cap items. Copy constructor with signature : template MedianHeap::MedianHeap(const MedianHeap& otherH) ; Destructor with signature : template MedianHeap::~MedianHeap() ; overloaded assignment operator with the signature: template const MedianHeap& MedianHeap::operator=(const MedianHeap& rhs) ; The assignment operator must deallocate memory in the host object and copy the rhs MedianHeap into the host. The MedianHeap class must have a member function called size() that returns the total number of items in the MedianHeap. The size() function must have the signature: template int MedianHeap::size() ; The MedianHeap class must have a member function called capacity() that returns the maximum number of items that can be stored in the MedianHeap. The capacity() function must have the signature: template int MedianHeap::capacity() ; The MedianHeap class must have a member function called insert() that adds the item given in the parameter to the MedianHeap. The insert() function must have the signature: template void MedianHeap::insert(const T& item) ; The MedianHeap class must have member functions called getMedian(), getMin() and getMax() that returns a copy of an object with the median, minimum and maximum keys, respectively. These functions should have the signatures: template T MedianHeap::getMedian() ; template T MedianHeap::getMin() ; template T MedianHeap::getMax() ; The MedianHeap class must have a member function called deleteItem with the following signature: template bool MedianHeap::deleteItem(T& givenItem, bool (*equalTo) (const T&, const T&) ) ; The deleteItem() function should look for an item stored in the MedianHeap that is equal to the givenItem parameter according to the equalTo() function. The equalTo() function does not have to determine equality based on the key value used by the MedianHeap. The MedianHeap class must have a member function called dump that prints out the contents of the MedianHeap including the positions of each key in the max heap and the min heap. See formatting examples in the sample output below. The dump() function must have the signature: template void MedianHeap::dump() ;