[Solved]: Finding the $k$th largest element in an evolving query data structure

Problem Detail: 

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.

Asked By : Chopra Jack

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2575