0
$\begingroup$

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

Improve this question
$\endgroup$
9
  • $\begingroup$ Please credit the original source for all copied material. $\endgroup$
    – D.W. ♦
    Nov 29, 2020 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, 2020 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, 2020 at 8:12
  • $\begingroup$ @D.W. I agree, thats why I wanted to ask here aswell $\endgroup$
    – convxy
    Nov 29, 2020 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, 2020 at 8:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.