existence of a certain data structure

Question

I'm wondering, can there exists such a data stucture under the following criterions and times(might be complicated)?

if we obtain an unsorted list L an build a data structure out of it like this:

• Build(L,X) - under O(n) time, we build the structure S from an unsorted list of n elements
• Insert (y,S) under O(lg n) we insert z into the structure S
• DEL-MIN(S) - under O(lg n) we delete the minimal element from S
• DEL-MAX(S) - under O(lg n) we delete the maximal element from S
• DEL-MId(S) - under O(lg n) we delete the upper medial(ceiling function) element from S

the problem is that the list L is unsorted. can such a data structure exist?

Answer 1

DEL-MIN and DEL-MAX are easy: keep a min-heap and max-heap of all the elements. The only trick is that you have to keep indices of the value in the heap so that when (for example) you remove the max, you can also find it and remove it in the min-heap.

For DEL-MED, you can keep a max-heap of the elements less than the median and a min-heap of the elements greater than or equal to the median. The full description is in this answer: Data structure to find median. Note that in that answer the floor-median is returned, but that's easily fixed. Again, you need to use the cross-indexing trick to refer to the other datastructures as in the first part. You will also need to think how this handles repeated elements if that's possible in your problem formulation. (If necessary, you can do it by storing repeated elements as (count, value) in your heap, but this complicates rebalancing the heaps on insert/remove a little).

Can this all be built in O(n)? Yes -- you can find the median of n things in O(n) time (using the median-of-median algorithm), and heaps can be built in O(n) time.

So overall, the datastructure is 4 heaps (a min-heap of all the elements, a max-heap of all the elements, a max-heap of the floor(n/2) smallest elements, a min-heap of the ceil(n/2) largest elements. All with cross-indexes to each other.