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.
```