5
$\begingroup$

Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element inserted so far.

I was solving the problem with segment trees, but I am not able to make a little modification to the query function of the segment tree. The query function that I wrote returns the largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$:

int query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)
{
    if (t_begin>=a_begin && t_end<=a_end)
        return Tree[Nodenumber];
    else
    {
        int mid=((t_begin+t_end)/2);
        int res = -1;

        if (mid>=a_begin && t_begin<=a_end)
            res = max(res,query(2*Nodenumber,t_begin,mid,a_begin,a_end));

        if (t_end>=a_begin && mid+1<=a_end)
            res = max(res,query(2*Nodenumber+1,mid+1,t_end,a_begin,a_end));

        return res;
    }
} 

Note to make a query, I call the query function as query(1,0,N-1,QA,QB).

But I want to return the $|A|/3$-th largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$. So how should I modify the function to do this?

So updating, queries, updating, queries, updating, queries and so on are done randomly and several (upto $10^5$) times.

So, for solving the problem, did I pick the right data structure? I thought of using heaps, but that will be too slow, as I would have to pop $|A|/3$ elements from the top and reinsert them for every query.

$\endgroup$
  • 1
    $\begingroup$ Welcome! Wow, that was barely legible. I edited to clarify the question; please check that I did not change the meaning. $\endgroup$ – Raphael Jul 2 '12 at 10:04
4
$\begingroup$

Have a look at the Wikipedia page for segment trees:

It is, in principle, a static structure; that is, its content cannot be modified once the structure is built.

So it does not seem to be a good data structure for your scenario at all.

Note that the kind of query you want to perform is called selection (unimaginative, I know). Check the linked article for loads of algorithms. One simple way to solve your problem is this:

  • Store elements in a sorted list. That means, updates (that is insertions) take linear time.
  • For the queries, run a selection algorithm on the specified interval.

This approach can be improved by extending the list to a skip list.

Another approach is using binary search trees. If you use a self-balancing variant, that makes updates possible in $O(\log n)$ time. The queries you want can be implemented by storing in every node how many descendants it has, so we can find the $k$-th largest element in $O(\log n)$ time.

$\endgroup$
  • $\begingroup$ :: Well I dont think the First one Selection algo will work.If there are N queries ,then I have to call Selection Algorithm N times, so overall worst case complexity will be O(N^2),as the time complexity for Selection Algorithm will is O(N).So can u please explain the idea of self-balancing in detail . Is there any stl in c++ for constructing Self Balancing Binary tree. Thanks! $\endgroup$ – Chopra Jack Jul 2 '12 at 14:31
  • $\begingroup$ @ChopraJack: Oh, it will work. You have not given runtime constraints in your question; do you have any? To be "precise", the total runtime will be $O(n(n+N))$ -- $n$ elements have to be inserted and $N$ queries are performed. Regarding self-balancing trees, please read the linked Wikipedia article and follow the links to implementations there. If you have problems with that material, you can ask a new question here. I'm afraid C++ libraries are off-topic here (and I really have no idea). $\endgroup$ – Raphael Jul 2 '12 at 19:16
1
$\begingroup$

You can use a segment tree to perform dynamic selection in $O(\log S)$ per oper; where $S$ is the size of the universe. To do this, you need to maintain the total number of elements in the segment represented by a node.

In fact, a binary indexed tree can also be used. Or you could also use a balanced binary search tree as Raphael suggested.

$\endgroup$
1
$\begingroup$

It is worth to mention that the problem is solvable with two heaps. You have to maintain a max heap for the first ~2[A]/3 element and a min heap for the last ~[A]/3 element. Inserting is O(log[A]), query is O(1).

$\endgroup$
  • $\begingroup$ Please provide an example. $\endgroup$ – CodeYogi Nov 4 '15 at 6:01

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.