You are not logged in. Please login at www.codechef.com to post your questions!

×

Merge sort tree in JAVA

Hello everyone, nowadays I frequently encounter some very interesting problems on merge sort tree. A few days back I tried with segment tree(with TreeSet in each node). Now TreeSet stores all the elements in sorted order and I merged two nodes with the addAll() operation but I encountered a TLE. I am really curious as of how merge sort tree is implemented in JAVA. As I know C++ has really a nice STL implementation of the function merge() for merging two vectors in sorted order.

asked 19 Jul, 21:58

aman_robotics's gravatar image

6★aman_robotics
1236
accept rate: 6%

edited 19 Jul, 22:01

Link to problem??

(19 Jul, 22:04) taran_14076★

doesnt treeset has an additional complexity of LOGN for accessing elements? Anyways you can merge 2 sorted arrays in O(N)

(19 Jul, 22:08) soham12346★

The recent long challenge which had a very interesting problem PDELIV : https://www.codechef.com/JULY18A/problems/PDELIV and the question I was talking about a TLE, is from a recent ongoing external contest so I don't want to discuss that problem as of now.

(19 Jul, 22:11) aman_robotics6★

PDELIV needed normal segment trees, merge sort trees werent needed. Anyways you can always write your own merge function. Below I am posting my own merge function so that you can have an idea

(19 Jul, 22:18) soham12346★
1

Yeah actually I needed to be clear with merging, as two nodes(segment tree) with CHT needed to be merged, I am stucked up as of how to do it efficiently.

(19 Jul, 22:31) aman_robotics6★

You dont need to merge in PDELIV. You just loop through all the lines in the range that current node covers and insert them in current nodes hull in sorted order.

(19 Jul, 23:35) soham12346★
showing 5 of 6 show all

What do you need to store on each node, a TreeSet or an ArrayList? If ArrayList, simple merge function can be implemented using two pointers, one for each child, inserting in current node vector in required order.

Similar thing can be done using Iterator for TreeSet with similar complexity.

Have a look for Iterator here.

link

answered 19 Jul, 22:08

taran_1407's gravatar image

6★taran_1407
3.7k2172
accept rate: 23%

        void combine(int pos1,int pos2,int pos)
    {
        int l=0,r=0;
        while(l<st[pos1].size() && r<st[pos2].size())
        {
            if(st[pos1][l]<st[pos2][r])
             st[pos].pb(st[pos1][l++]);
            else
             st[pos].pb(st[pos2][r++]);
        }

        while(l<st[pos1].size()) st[pos].pb(st[pos1][l++]);
        while(r<st[pos2].size()) st[pos].pb(st[pos2][r++]);
    }
link

answered 19 Jul, 22:19

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

Well you refer this resource on java treeset iterator example.

link

answered 30 Sep, 13:58

siddarthprakas's gravatar image

0★siddarthprakas
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,253
×795
×699
×74
×28

question asked: 19 Jul, 21:58

question was seen: 244 times

last updated: 30 Sep, 13:58