I've got this question from an exercise and i'm not sure if it is possible to do so
Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations:
Insert(v,Q) which insert into Q (no time complexity constrain here)
Delete-Median(v,Q) which takes the median out of Q in $O(1)$
The question is, What data do you store in your data structure and write pseudocode for both operations
I've thought about using binary search tree and when I insert I will try to make the tree as balanced as possible but when i delete the median( which is the root) I need to rearrange the tree and it won't be $O(1)$ and I'm not sure if it's possible to delete in $O(1)$ but I know that I show "print" the median in $O(1)$
Any help would be appreicaited