Nice Soln Lucifer, i had problem of tracking kth value when coming across two siblings, each sibling has many childs so i think a bottom up approach would be better for finding number of elements(say* y*) <x finally at root we have y, if y<=k then kth element is < x else kth elemnt is >x
Surender On Sun, Dec 18, 2011 at 12:49 AM, Lucifer <[email protected]> wrote: > @atul.. > Complexity would be 2(n-k+1) = O(2*(n-k)) .... > > Basically the condition based on which the traversal is performed willow > change. I have modified some part of the original post to show that: > > Instead of having the initial count as K have it as N-K+1 .. when > taking a max-heap.. > > To solve the problem we need to do a pre-order traversal keeping the > following conditions in mind: (pass K and root node) > 1) If current node is < X then skip the processing of the tree rooted > at the current node. > 2) If current node is >= X , then decrement the initial count i.e (n-k > +1) by 1 and process its > childs ( i.e take step 1 for rach child). > The result will depend on: > a) If at any stage recursion ends and the value of initial count >0 > then the kth > smallest element is < X. > b) If during tree traversal the value of initial count reaches 0, > that means > there are atleast (n-k+1) elements which are >= X. Hence, at this > point > terminate the recursion ( as in no need to continue). This result > signifies that the kth smallest element >= X. > > On Dec 17, 1:28 pm, atul anand <[email protected]> wrote: > > @Lucifer : if for the same question , we consider a Max heap instead of > Min > > heap then complexity of the same algo will be O(N) ... right??? > > > > > > > > > > > > > > > > On Fri, Dec 16, 2011 at 8:50 PM, Lucifer <[email protected]> wrote: > > > @my previous post.. > > > > > While explaining the run-time I have made an editing mistake... > > > instead of 'N' nodes it should be 'K' nodes.. > > > i.e. > > > Hence, for any given bin- tree having 'K' nodes, the number of null > > > nodes is 'K+1'. > > > These null nodes are nothing but the nodes where the check nodeValue < > > > X failed while traversing the original tree. > > > Hence, the total number of checks will be 2K+1 = O(2K) > > > > > On Dec 16, 1:04 am, sunny agrawal <[email protected]> wrote: > > > > oops... > > > > wanted to write the same but yeah its meaning turns out to be totally > > > > different :( > > > > anyways very well explained by Lucifier > > > > > > @shashank > > > > i think now u will be able to get why there will be only 2k > comparisons > > > in > > > > the worst case > > > > > > On Thu, Dec 15, 2011 at 10:51 PM, atul anand < > [email protected] > > > >wrote: > > > > > > > @Lucifer : yes even i found flaw in the above algo when i gave it a > > > second > > > > > thought but didnt get time to post it. > > > > > bcoz min heap has property that the parent node is less than its > both > > > > > child(subtree to be more precise ) but it does not confirm that > left > > > child > > > > > is always smaller than right child of the node. > > > > > > > On Thu, Dec 15, 2011 at 10:31 PM, Lucifer <[email protected]> > > > wrote: > > > > > > >> @All > > > > > > >> I don't think the algo given above is entirely correct.. Or may > be i > > > > >> didn't it properly... > > > > > > >> So basically say a preorder traversal of the heap is done based on > > > > >> whether the current root value < X. As the algo says that at any > point > > > > >> if k>0 and we hit a node value which is >=X , then we are done. > If i > > > > >> understood it properly then thats not correct. > > > > > > >> The reason being that say on the left subtree we end up at a node > > > > >> whose value is >=x and say k > 0. Now until and unless we don't > parse > > > > >> the right subtree (or basically the right half which was > neglected as > > > > >> part of pre-order traversal or say was to be considered later) we > are > > > > >> not sure if the current node is actually withing the first > smallest K > > > > >> nos. It may happen that previously neglected (or rather later to > be > > > > >> processed) half has the kth smallest element which is actually < > X. > > > > >> The reason being that a heap is not a binary search tree where > there > > > > >> is a strict relation between the left and the right half so that > we > > > > >> can say that if say a condition P is true in the left half then it > > > > >> will be false in the right half and vice versa. > > > > > > >> To solve the problem we need to do a pre-order traversal keeping > the > > > > >> following conditions in mind: (pass K and root node) > > > > > > >> 1) If current node is >= X then skip the processing of the tree > rooted > > > > >> at the current node. > > > > > > >> 2) If current node is < X , then decrement K by 1 and process its > > > > >> childs ( i.e take step 1 for rach child). > > > > > > >> The result will depend on: > > > > > > >> a) If at any stage recursion ends and the value of K>0 then the > kth > > > > >> smallest element is >= X. > > > > >> b) If during tree traversal the value of K reaches 0, that means > > > > >> there are atleast k elements which are < X. Hence, at this point > > > > >> terminate the recursion ( as in no need to continue). This result > > > > >> signifies that the kth smallest element < X. > > > > > > >> Therefore to generalize... > > > > > > >> Perform a preorder traversal for root node < X, and keep > decrementing > > > > >> the count K by 1. > > > > >> If K reaches 0 during traversal then end the recursion. > > > > > > >> After the call to the recursive traversal is over, check for the > value > > > > >> of K. If greater than 0, then the kth smallest element >= X > otherwise > > > > >> its not. > > > > > > >> The time complexity will always be 2K ( in the worst case > basically > > > > >> when K value reaches 0 ). If u analyze it closely we are making 2 > > > > >> checks when at particular node for its children. Hence, whether > both > > > > >> the child nodes have value < X or one of them or node, at the end > we > > > > >> always end up making 2 checks for the children (left and right > child). > > > > >> So given any tree one can think of a null node as a leaf node > > > > >> ( depicting that the node has a value >=X) . Hence, for any given > bin- > > > > >> tree having nodes 'N', the number null nodes is 'N+1'. Hence, the > > > > >> total number of checks will be 2N+1 = O(2N) , > > > > > > >> On Dec 15, 1:00 pm, WgpShashank <[email protected]> > wrote: > > > > >> > @sunny why we look at all k number which are greater then x , > > > correct ? > > > > >> > Lets think in this way > > > > > > >> > we wants to check if kth smallest element in heap thats >=x > isn't > > > it ? > > > > >> so > > > > >> > if root of mean heap is greater then x then none other elements > will > > > > >> less > > > > >> > then x so we terminate . > > > > >> > else our algorithm will search children of all the nodes which > are > > > less > > > > >> > then x till either we have found k of them or we are exhausted > e.g. > > > > >> when > > > > >> > k=0 . so we will cal our function to both left & right children > ? > > > > > > >> > so now think we are looking for children's of only nodes which > are > > > less > > > > >> > then x and at most k of these in tottal . each have atmost two > > > visited > > > > >> > childrens so we have visted at-most 3K nodes isn;t it ? for > total > > > time > > > > >> O(K) > > > > >> > ? > > > > > > >> > let me know where i am wrong ? i am not getting for uy k nodes > > > greater > > > > >> then > > > > >> > x ? why we will do that & then how much comparisons u needs for > > > that ? > > > > > > >> > Thanks > > > > >> > Shashank Mani > > > > >> > CSE, BIT Mesrahttp://shashank7s.blogspot.com/ > > > > > > >> -- > > > > >> You received this message because you are subscribed to the Google > > > Groups > > > > >> "Algorithm Geeks" group. > > > > >> To post to this group, send email to [email protected]. > > > > >> To unsubscribe from this group, send email to > > > > >> [email protected]. > > > > >> For more options, visit this group at > > > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > > > -- > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to [email protected]. > > > > > To unsubscribe from this group, send email to > > > > > [email protected]. > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > > > > Sunny Aggrawal > > > > B.Tech. V year,CSI > > > > Indian Institute Of Technology,Roorkee > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
