LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations

Question

Consider a data structure called LazyHeap that supports the following operations:

• INSERT(x): Given an element $x$, insert it into the data structure. It has no cost.

• DELETE(x): Delete $x$ from the data structure. It has no cost.

• RETURN: Return an element $x$ such that its order, if the elements are sorted, satisfies:

  $$k/2 - k/100 \le \mathrm{order}(x) \le k/2 + k/100\,,$$

  where $k$ is the number of elements in the data structure (at the time RETURN is called). RETURN also has no cost.

Come up with a strategy for the comparisons so that the running time for any sequence of $n$ operations is less than $1000n$.

I know that sometimes you have to make comparisons between two elements so that you can perform RETURN operation correctly, where one comparison costs one unit. However, I'm not sure where to go from there. Any help would be appreciated!

Answer 1

I can't actually see an approach that would provide constant time insert and return of the mid-element in $O(1)$ (and I understand "no cost" to be some constant cost.) I have, however, some ideas that may suggest some solution.

One approach that comes to my mind are two heaps, one MIN and one MAX. The MIN heap would keep al elements greater than the current mid element (satisfying $\frac{k}{2} - \frac{k}{100} ≤ midElement ≤\frac{k}{2} + \frac{k}{100}$) and the MAX heap would store all smaller or equal ones. On INSERT(x) we'd need to keep the heaps as balanced as possible, so we would compare x with the current mid element, add it to the proper heap (MIN if x > midElement, else MAX) and if the difference between heaps' sizes would grow larger than 1, we'd take an element from the larger one and insert it to the smaller one. However, RETURN would work in $O(log(n))$, as after returning the top of one of the heaps we would need to repair that heap. INSERT would also take $O(log(n))$ and DELETE could be even linear (select the heap in $O(1)$, get to the proper level of it (elements on lower level are too too big/too small) and search the level in $O(n)$).

Another approach would be to keep a balanced tree (like RB-Tree or an AVL-Tree). The top element would always be the mid-element. However, here RETURN would also work in $O(log(n))$ because we'd need to reset the root after removing it. INSERT would also work in $O(log(n))$ for the insert itself + eventual balancing and so would DELETE.

Constant times required ("has no cost") brings Hash-tables to mind. Average INSERT would indeed take $O(1)$ and so would DELETE (if table size and hashing function would be properly designed). As for RETURN - one approach would be to track the inserted elements and keep the index of the current mid-element. If greater or smaller elements were inserted we'd consider selecting the "next mid-element", but this would probably require $O(n)$ time (or at least I can't see any other way doing it). So this would actually cause our RETURN to work in $O(1)$ (if we keep an index of the mid-element), but grow INSERT cost to $O(n)$ (and similarly for DELETE.)