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

  • $\begingroup$ Please credit the original source for all copied material. $\endgroup$ – D.W. Nov 29 '20 at 8:11
  • $\begingroup$ I'm doing a course in the university and it's not an official book of data-structures. $\endgroup$ – convxy Nov 29 '20 at 8:12
  • $\begingroup$ Are you sure those are the only two operations? Neither operation returns anything, so the implementation of both operations could be "do nothing" and that would be correct as far as you could observe externally. Something seems missing. $\endgroup$ – D.W. Nov 29 '20 at 8:12
  • $\begingroup$ @D.W. I agree, thats why I wanted to ask here aswell $\endgroup$ – convxy Nov 29 '20 at 8:14
  • $\begingroup$ You'll need to ask your instructor. If you don't understand what the question is asking, how can we be expected to understand it? Your question asks us to find an algorithm -- it's your responsibility to make sure the post here clearly specifies the requirements for that algorithm. If you are not clear what the requirements are, then it is premature to ask us here how to find an algorithm that meets those unknown requirements. $\endgroup$ – D.W. Nov 29 '20 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.