This Forum is in read only mode now.

You are not logged in. Please login at 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 '18, 21:58

aman_robotics's gravatar image

accept rate: 6%

edited 19 Jul '18, 22:01

Link to problem??

(19 Jul '18, 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 '18, 22:08) soham12346★

The recent long challenge which had a very interesting problem 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 '18, 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 '18, 22:18) soham12346★

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 '18, 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 '18, 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.


answered 19 Jul '18, 22:08

taran_1407's gravatar image

accept rate: 22%

        void combine(int pos1,int pos2,int pos)
        int l=0,r=0;
        while(l<st[pos1].size() && r<st[pos2].size())

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

answered 19 Jul '18, 22:19

soham1234's gravatar image

accept rate: 22%

Well you refer this resource on java treeset iterator example.


answered 30 Sep '18, 13:58

siddarthprakas's gravatar image

accept rate: 0%

edited 24 Sep, 20:00

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 19 Jul '18, 21:58

question was seen: 382 times

last updated: 24 Sep, 20:00