median - how to design a data structure that getMedian and insert in O(1)?

Question

I thought about doing this in sort array and save the index of the median and its takes O(1). but I couldn't think about any way to do the insert in O(1) and keep the array sorted. I really appreciate it if someone can help me with this problem

question from:https://stackoverflow.com/questions/65874480/how-to-design-a-data-structure-that-getmedian-and-insert-in-o1

Answer 1

What you are asking for is impossible, because it would allow comparison-based sorting in O(n) time:

• Suppose you have an unsorted array of length n.
• Find the minimum element and maximum element in O(n) time.
• Insert all n elements into the data structure, each insertion takes O(1) time so this takes O(n) time.
• Insert n-1 extra copies of the minimum element. This also takes O(n) time.
• Initialise an output array of length n.
• Do this n times:
  • Read off the median of the elements currently in the data structure, and write it at the next position into the output array. This takes O(1) time.
  • Insert two copies of the maximum element into the data structure. This takes O(1) time.

The above algorithm supposedly runs in O(n) time, and the result is a sorted array of the elements from the input array. But this is impossible, because comparison-sorting takes Ω(n log n) time. Therefore, the supposed data structure cannot exist.