2
$\begingroup$

I'm looking for a data structure, in which the operations $Init, Median, Min, Max, Delete$ run in $O(1)$ amortized-time, and $Insert$ should run in amortized-time as low as possible.

I tried to work with Min-Max Fibonacci heaps and pointer to median, but got stuck.

I believe the $Insert$ operation can be done in $O(\log n)$ amortized-time.

Any help is appreciated.

Improve this question
$\endgroup$
4
  • $\begingroup$ Amortized over what sequence of operations? $\endgroup$
    – Raphael ♦
    Feb 18, 2018 at 16:32
  • $\begingroup$ @Raphael I believe that it should be for any sequence of operations. $\endgroup$
    – Itay4
    Feb 18, 2018 at 16:48
  • $\begingroup$ Consider using two priority queues, one up to current median and the other up from median. $\endgroup$
    – Omar
    Feb 18, 2018 at 17:11
  • $\begingroup$ @Omar Yes, that's what I've tried, but couldn't proceed. Mind elaborating ? $\endgroup$
    – Itay4
    Feb 18, 2018 at 17:21

1 Answer 1

Reset to default
1
$\begingroup$

It should be possible with everything O (1) amortized if the insertions and deletions are random: If there are n items, try to keep track of the sqrt (n) smallest items, largest items, and items around the median.

If you insert or remove an item within the smallest, largest or median items, that's $O(n^{1/2})$ because you need to insert or remove one of $n^{1/2}$ elements, and happens with probability $O(1/n^{1/2})$, so total O (1).

Whenever you insert or remove one of the elements before the median elements, the range of the "median" elements shifts. When the items that were supposed to be around the median don't contain the median element anymore, you need to find elements around the median again, which should happen in O (n). If insertion / deletions are random, then I think the balance shifts by $n^{1/2}$ only after a large number of insertions / deletions. You'll have to check the maths.

And of course all this only works if insertions / deletions are random. Otherwise you need something significantly more clever.

PS. D.W.'s comment indicates (unless I'm very wrong) that if you can find the median and insert items in O (f(n)) amortized in the worst case, then you can sort an array in O (n·f(n)), which means f(n) cannot be better than log n asymptotically in the worst case.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The assumption of randomness is crucial. I don't think you can achieve this running time in worst-case. Otherwise, you could sort in $O(n)$ time. To sort $x_1,\dots,x_n$, first insert $n$ numbers that are smaller than all of the $x_i$'s; then insert $x_1,\dots,x_n$, then repeat the following $2n$ times: query the median, and insert a number larger than all the $x_i$'s. These queries will return the numbers $x_1,\dots,x_n$ in sorted order. In total this involves doing $6n=O(n)$ operations on the data structure. $\endgroup$
    – D.W. ♦
    Mar 20, 2018 at 21:39
  • $\begingroup$ Very clever :-) Of course my proposal relies on randomness to make sure the values around the median only need to be found after about N changes; since you are always adding an element larger than the median you have to find the median values again after about $N^{1/2}$ steps which gives you $O(N^{1.5})$ for sorting the array. $\endgroup$
    – gnasher729
    Apr 19, 2018 at 21:41

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.