2
$\begingroup$

Consider a data structure that has only two functions. extract_lowerthan_median() and insert(). How can we design it in a way that the amortized cost for both the operation is O(1)?

Using a 2 tree, a min heap and max heap will ensure that the root of min heap is always the median and allow us to extract an element smaller than median with O(1) cost. However, the insertion would run in O(logn). Since we could amortize these cost there should be a structure which performs both these operations in O(1) where we somehow mask the cost of insertion in extraction but I cant think of anything

$\endgroup$
6
  • 2
    $\begingroup$ Hint: use Partition function from the Quicksort algorithm. In particular, take a look at CLRS, 3ed, Section 9 "Medians and Order Statistics". $\endgroup$
    – Dmitry
    Commented Oct 9, 2022 at 23:10
  • $\begingroup$ @Dmitry I dont understand? The quickselect derivative of the quick sort uses randomized pivot selection to find the median in average case O(n) but in my query I want to design a data structure with O(1) insertion and finding element smaller than median? $\endgroup$ Commented Oct 9, 2022 at 23:36
  • 1
    $\begingroup$ Yes. The keyword is "amortized". Another Hint: think about how the ArrayList gets $O(1)$ amortized time (although some changes are required here). $\endgroup$
    – Dmitry
    Commented Oct 9, 2022 at 23:49
  • $\begingroup$ Another hint: the medians of medians algorithm finds the exact median in $O(n)$. It can be modified to find the $k$-th smallest element in $O(n)$. $\endgroup$
    – plshelp
    Commented Oct 10, 2022 at 9:10
  • 1
    $\begingroup$ Can you clarify, what exactly does extract_lowerthan_median means? Is it allowed to extract an arbitrary element less than the median? I was thinking, wouldn't it break the lower bound for comparison based sorting if we have $O(1) $ amortized for the two operations? Since the extract_lowerthan_median can be implemented for it to remove and return the current min element, which is less than the median. $\endgroup$
    – Russel
    Commented Oct 10, 2022 at 12:15

2 Answers 2

3
$\begingroup$

Amassing many elements significantly lower than median at once

The basic idea is to maintain a list of small elements that are guaranteed to be lower than median. Also maintain a list of all other elements that may or may not be lower than median, which will accept all new elements.

extract_lowerthan_median pops an element from the list of small elements most of the time. insert appends a new element to the list of other elements most of the time.

When there is no "small elements" or there are too many "other elements", the two lists will be adjusted so that the list of small elements will contain the $\lfloor n/4\rfloor$ smallest elements of all current elements, which can be selected using $O(n)$ operations. The very low frequency of this adjustment ensures the amortized cost of both extract_lowerthan_median and insert be $O(1)$.

The data structure in detail

For simplicity, assume no two numbers are equal.

Assume the median means the middle number when $n$ is odd or the mean of the middle two numbers when $n$ is even. "A number lower (smaller) than median" means any number that is smaller than the median. With the assumption of no equal numbers, a number among the given numbers lower than median also means a number such that the number of numbers larger than it is not smaller than the number of numbers not larger than it.

Build a data structure $D$ with two disjoint (unsorted) lists and a number,

  • small_nums, a list of small numbers, which is empty initially,
  • other_nums, a list of numbers, which is empty initially,
  • capacity, a natural number, which is $0$ initially,

with three functions:

  • extract_lowerthan_median():

    1. If small_nums is empty,
      1. If len(other_nums) < 8, return accordingly. That means, if the smallest element is lower than median, pop it from other_nums and return it. Otherwise, return none. (len(a_collection) is the number of elements in a_collection.)
      2. Else, call amass_small_numbers()
    2. Pop an element from small_nums and return it.
  • insert(new_num):

    1. Append new_num to other_nums.
    2. If len(other_nums) > 5 * capacity, call amass_small_numbers(). This step ensures any element poped from small_nums will be lower than median.
  • amass_small_numbers():

    1. Move all numbers in small_nums into other_nums.
    2. set capacity to len(other_nums)//4. (// is the integer division such as 7//3=2). Note that capacity is guaranteed to $\ge2$.
    3. Find the (capacity + 1)-th smallest element in other_nums, using a linear-time $k$-th-smallest-element selection algorithm as explained here or here. Denote it by p.
    4. Move all capacity elements in other_nums that are smaller than p to small_nums.

Some minor variations.

  • greybeard suggested that insert(new_num) at step 1 add new_num to small_nums instead of other_nums if new_num < p, where p is the pivot computed in the last call to amass_small_numbers. (If not, add to other_nums as before.)

    To implement this variation, the data structure should have one additional variable to store that pivot p and another additional variable pop_count to store the number of calls to extract_lowerthan_median since last call to amass_small_numbers. The condition len(other_nums) > 5 * capacity at the step 2 of insert(new_num) should then be replaced by len(other_nums) >= 8 and (len(small_nums) + len(other_nums) + pop_count > 6 * capacity or len(small_nums) == 0).

    This variation may boost the performance, especially when there are lots of extract_lowerthan_median.

  • Dmitry presented a simplified version.

    After amassing the $n/4$ smallest numbers, call extract_lowerthan_median and insert() at most $n/4$ times together. Neither extract_lowerthan_median nor insert calls amass_small_numbers.

$\endgroup$
0
1
$\begingroup$

John's answer is probably correct, but I just want to present a simple version that demonstrates the idea (in particular, I ignore the cases when $n$ is small, when there are duplicates, or when $4$ doesn't divide $n$; you can figure them out):

Let A be the initial array
while true:
    n := A.length
    Small := n/4 smallest elements of A, in any order
    Others := the rest of the elements of A
    process the next n/4 queries:
        For insert queries: add the new element to Others
        For extract queries: extract any element from Small
    A := (arbitrary) concatenation of Small and Others

You can find Small and Others in $O(n)$ using QuickSelect.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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