Actually this problem is very similar to one of the problem in my algorithm design class, here is the full version for it. Hope you are interested.
1. Design a data structure that has the following properties (assume n elements in the data structure, and that the data structure properties need to be preserved at the end of each operation): • Find median takes O (1) time • Extract-Median takes O (log n ) time • Insert takes O (log n ) time • Delete takes O (log n ) time Do the following: (a) Describe how your data structure will work. (b) Give algorithms that implement the Extract-Median() and Insert() functions.