# Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time

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.

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

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.
• 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. – D.W. Mar 20 '18 at 21:39
• 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. – gnasher729 Apr 19 '18 at 21:41