Segment Tree Kth Maximum

Question

Hi I was solving the problem on a segment tree,But I am not able to make a little modification to the query function of segment tree .

Actually What I want is my query function should return the (int)(TotalArrayLength/3) th maximum element between index Qa and Qb.

The Query Function that I wrote Returns the Maximum element between index[1-based] a_begin and a_end.

But I want to return the (int)(TotalArrayLength/3)th Maximum element between index[1-based] a_begin and a_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).

Also I implemented the following Pseudo-code to write above query Function,

So How should I modify to find (int)(TotalArrayLength/3)th Maximum element between index[1-based] a_begin and a_end.

Basically ,the problem I am solving is :

Initially the array contains 0 or more element. Randomly some data is to be inserted at the end of the array and at any time a query is to be done that return TotalArraySize/3 th Max Elements in Array build so far.

Also ,did I select the right data structure for the purpose.

Thanks a lot.

Answer 1

My first though is:

You'll need to use a K sized sorted list as a return value for each query() call. If the query lies fully to the left or the right of the mid-point then return that result. If the query straddles the mid point then merge the result of each child when they return. Once you get back to the root then you return the kth element in the resulting sorted list.

The method signature (in Java) would be:

List<Integer> query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)

A max heap data structure could accomplish the same job. Just build the max-heap from the items between the indices and pop off the head k times.

A segment tree would be good at multiple queries where a heap would be better in terms of overall memory and single queries on the data.