×

# Merge sort tree in JAVA

 0 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 120●7 accept rate: 6% Link to problem?? (19 Jul '18, 22:04) 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) 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 '18, 22:11) 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) 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 '18, 22:31) 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) showing 5 of 6 show all

 1 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 4.0k●31●104 accept rate: 22%
 1  void combine(int pos1,int pos2,int pos) { int l=0,r=0; while(l
 0 Well you refer this resource on java treeset iterator example. answered 30 Sep '18, 13:58 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,313
×849
×711
×74
×28

question asked: 19 Jul '18, 21:58

question was seen: 333 times

last updated: 30 Sep '18, 13:58