How HEAPULM from spoj can be solved by segment tree.

HEAPULM problem from Spoj can be solved by recursion, by making binary search tree of nodes of sorted priority and then performing an inorder traversal of the BST. But how can it be solved by using segment tree?
This problem is categorized under segment tree in
praveendhinwa’s blog

sorry to keep you waiting!

my approach : first of all i used the fact that inorder traversal leads to a sorted result. so, at first i sort the given nodes in ascending order and then build the tree (which previously takes O(N^2)) in O(N)!

see the node at the root is the node with highest priority(val in my code) and so, i just select the node with highest priority from the sorted list and make it root and since it is a BST so, all the nodes to the left of the curr_index(index of highest priority) belong to the left sub-tree and those which are in the right part belong to the right sub-tree and then recursively build each of the left and right sub-tree.

The segment tree is used to answer the query : what is the position of the node with highest priority in a range(l, r).

code : wSaUA7 - Online C++0x Compiler & Debugging Tool - Ideone.com

hope it helps! if you have any doubts in the code or in understanding approach please comment :slight_smile:
and if you find this helpful please accept the answer!

3 Likes

Thank you for your answer, before I go through your segment tree approach, could you please help me out where I am going wrong in this BST approach

My approach: I have sorted the array of pairs (containing priority and label) on the basis of increasing priority.
And then tried to make Binary search tree from highest priority pair to lowest priority pair. The inorder traversal of this BST will give the desired answer.

@chan55555

if(p[i].S<p[root->index].S)

here you are comparing with the root but the new root now is t !

1 Like

Many thanks for pointing that mistake, I was having a hard time debugging my code. But as you have pointed earlier, it’s producing TLE, due to O(N) time complexity of insertion of a node in BST. Now going to read about your approach.

I have accepted your answer. But I have a doubt. In your approach, you sorted the array of pair based on the label of the nodes and then used segment tree approach to find the max priority of the node in the given range (l,r), to build the treap. Time complexity of your process is O(N^2+N*log(N)).

In my approach, I have sorted the array of pair based on the priority of the nodes and then tried to make binary search tree of nodes from higher priority to lower priority, where inserting of a node also takes logarithmic of time or can say O(h) where h is height of tree (but in case of skew trees(first sample case) time complexity of insertion of a node in O(N) ). My solution’s time complexity is also same as yours but my solution is giving TLE. Is this because of the cases where the tree is the skew tree.??

@chan55555 time complexity of creating a segment tree with N base elements is O(N) and here i have created tree with O(N) nodes and so, building segment tree is O(N) and querying the tree will take O(logN) and i am querying N times(for each node) and so time here is O(NlogN). Now as far as sorting is concerned it is straight forward O(NlogN) and so overall complexity will O(NlogN)!

but in your approach as you can see it is staright forward O(N^2)!

are you sure that " by making binary search tree of nodes of sorted priority and then performing an inorder traversal of the BST" will work ?

because the value of n here is 50000 which gives TLE as inserting a node may take O(N) (first sample case)!

But, I have already sorted the array of pairs and inserting the nodes with higher priority to the lower priority order. So while inserting a node in BST all other existing nodes will have higher priority than the node being inserted.

sorry mate i didn’t see that. i have updated my answer !

1 Like

glad to hear that :slight_smile:

Ok. I was assuming sort function as having O(n^2) of time complexity, but it is O(nlogn).

no problem :slight_smile:

Building BST using segment tree, seems like a useful trick, especially when elements are coming one by one.