3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ "no cost" -- in the (unrealistic) model, or do we have to ensure it (impossible)? What is the cost measure? $\endgroup$ – Raphael Dec 15 '14 at 18:44
1
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ I like all three of your approaches - I'm going to look into more details regarding them. Thank you so much! Do you believe order statistics (select algorithm - median of medians) would help over here? $\endgroup$ – TheVarunShah Dec 15 '14 at 19:03
  • $\begingroup$ I am not sure (can't see their application here at the moment), but it is possible, especially where I suggested we'd need to perform linear-searching. However, note that simple algorithms for order statistics work at least in O(n). If my suggestions were helpful, you may consider marking my answer as "accepted" (and although I am new here myself - welcome to CS Stack Exchange.) $\endgroup$ – 3yakuya Dec 15 '14 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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